# Construct an Array of length N containing exactly K elements divisible by their positions

Given two integers N and K, the task is to construct an array of length N containing exactly K elements visible by their positions.

Examples:

Input: N = 6, K = 2
Output: {5, 1, 2, 3, 4, 6}
Explanation: Considering the above array:
At Position 1, element 5 is divisible by 1
At Position 2, element 1 is not visible by 2
At Position 3, element 2 is not visible by 3
At Position 4, element 3 is not visible by 4
At Position 5, element 4 is not visible by 5
At Position 6, element 6 is divisible by 6
Therefore, there are exactly K elements in array divisible by their positions, meeting the required criteria.
Hence the resultant array will be {5 1 2 3 4 6}.

Input: N = 5, K = 5
Output: {1, 2, 3, 4, 5}

Approach: The problem can be solved easily using Greedy approach based on below observations:

For any integer X, we know that:

• X will be visible by 1 and X always.
• No integer greater than X will ever be able to divide X.

So using these observations, we can construct the array containing exactly K elements divisible by their positions, as follows:

• For position 1, place any element greater than 1, because 1 will divide all integers
• For positions greater than 1, choose K-1 positions, and place them in the array at corresponding indices.
• The remaining NK positions can be placed at any other position to match the required criteria.

Illustrations:

Consider an example: N = 6, K = 5

The empty array of size 6 will be:
arr[]: __ __ __ __
positions: 1 2 3 4 5 6

Step 1: Fill position 1 with any integer greater than 1

• For 1st value equal to its position, we have 2 options – to insert 1 at 1, and to insert some integer greater than 1 at 1. If we insert 1 at 1, there will be a case when we cannot have K=5 values same as their positions. So we will insert some other value greater than 1 at position 1 (say 5):
• arr[]: 5 __ __ __
positions: 1 2 3 4 5 6

Step 2: Fill K-1 (=4) positions at corresponding indices

• For 2nd value equal to its position:
• arr[]: 5 2 __ __ __
positions: 1 2 3 4 5 6
• For 3rd value equal to its position:
• arr[]: 5 2 3 ___
positions: 1 2 3 4 5 6
• For 4th value equal to its position:
• arr[]: 5 2 3 4 _ _
positions: 1 2 3 4 5 6
• For 5th value equal to its position, we cannot insert 5 at position 5, as it is already used at position 1. So we will insert 1 at position 5, and 6 at position 6:
• arr[]: 5 2 3 4 1 6
positions: 1 2 3 4 5 6

Therefore the final array will be: 5 2 3 4 1 6

Follow the steps below to implement the above approach:

• Create an array of N consecutive positive integers from 1 to N.
• After the index NKthere will be K-1 elements left, we will not interfere with these elements. So, we have K-1 elements, which are visible by their position.
• We will make the first element of the array equal to the element at index NK. This would also be visible by its position.
• We will make the remaining elements (ie from index 1 to NK) equal to the elements immediate left to them. These all NK elements will not be visible by their position then and remaining K elements would be visible by their position.

Below is the implementation of the above approach:

## C++

 `#include ` `using` `namespace` `std;` ` ` `vector<``int``> constructArray(``int` `N, ``int` `K)` `{` `    ` `    ``vector<``int``> A(N, 0);` ` ` `    ` `    ``for` `(``int` `i = 0; i < N; i++) {` `        ``A[i] = i + 1;` `    ``}` ` ` `    ` `    ` `    ` `    ``int` `target = N - K;` ` ` `    ` `    ` `    ``int` `prev = A;` ` ` `    ` `    ` `    ``A = A[target];` ` ` `    ` `    ` `    ` `    ` `    ``for` `(``int` `i = 1; i <= target; i++) {` `        ``int` `temp = A[i];` `        ``A[i] = prev;` `        ``prev = temp;` `    ``}` ` ` `    ``return` `A;` `}` ` ` `int` `main()` `{` `    ``int` `N = 6, K = 2;` ` ` `    ` `    ` `    ``vector<``int``> A = constructArray(N, K);` ` ` `    ` `    ``for` `(``int` `i = 0; i < N; i++)` `        ``cout << A[i] << ``" "``;` `    ``cout << endl;` `}`

Time Complexity: O(N)
Auxiliary Space: O(N)