# Assemble an Array of size N containing precisely Okay parts divisible by their positions Given two integers N and Okay, the duty is to assemble an array of size N containing precisely Okay parts divisible by their positions.

Examples:

Enter: N = 6, Okay = 2
Output: {5, 1, 2, 3, 4, 6}
Clarification: Contemplating the above array:
At Place 1, factor 5 is divisible by 1
At Place 2, factor 1 isn’t divisible by 2
At Place 3, factor 2 isn’t divisible by 3
At Place 4, factor 3 isn’t divisible by 4
At Place 5, factor 4 isn’t divisible by 5
At Place 6, factor 6 is divisible by 6
Subsequently, there are precisely Okay parts in array divisible by their positions, assembly the required standards.
Therefore the resultant array can be {5 1 2 3 4 6}.

Enter: N = 5, Okay = 5
Output: {1, 2, 3, 4, 5}

Method: The issue will be solved simply utilizing Grasping strategy primarily based on under observations:

For any integer X, we all know that:

• X can be divisible by 1 and X all the time.
• No integer better than X will ever be capable of divide X.

So utilizing these observations, we are able to assemble the array containing precisely Okay parts divisible by their positions, as follows:

• For place 1, place any factor better than 1, as a result of 1 will divide all integers
• For positions better than 1, select Okay-1 positions, and place them within the array at corresponding indices.
• The remaining N-Okay positions will be positioned at some other place to match the required standards.

Illustrations:

Contemplate an instance: N = 6, Okay = 5

The empty array of dimension 6 can be:
arr[]:         _  _ _  _ _  _
positions: 1 2 3 4 5 6

Step 1: Fill place 1 with any integer better than 1

• For 1st worth equal to its place, now we have 2 choices – to insert 1 at 1, and to insert some integer better than 1 at 1. If we insert 1 at 1, there can be a case after we can’t have Okay=5 values identical as their positions. So we’ll insert another worth better than 1 at place 1 (say 5):
• arr[]:         5 _ _  _ _  _
positions: 1 2 3 4 5 6

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

• For 2nd worth equal to its place:
• arr[]:         5 2 _  _ _ _
positions: 1 2 3 4 5 6
• For third worth equal to its place:
• arr[]:         5 2 3  _ _ _
positions: 1 2 3 4 5 6
• For 4th worth equal to its place:
• arr[]:         5 2 3 4 _ _
positions: 1 2 3 4 5 6
• For fifth worth equal to its place, we can’t insert 5 at place 5, as it’s already used at place 1. So we’ll insert 1 at place 5, and 6 at place 6:
• arr[]:         5 2 3 4 1 6
positions: 1 2 3 4 5 6

Subsequently the ultimate array can be: 5 2 3 4 1 6

Observe the steps under to implement the above strategy:

• Create an array of N consecutive optimistic integers from 1 to N.
• After the index N-Okay, there can be Okay-1 parts left, we won’t intervene with these parts. So, now we have Okay-1 parts, that are divisible by their place.
• We’ll make First factor of the array equal to the factor at index N-Okay. This might even be divisible by its place.
• We’ll make the remaining parts (i.e. from index 1 to N-Okay) equal to the weather instant left to them. These all N-Okay parts won’t be divisible by their place then and remaining Okay parts can be divisible by their place.

Beneath is the implementation of the above strategy:

## C++

 `#embrace ` `utilizing` `namespace` `std;` ` `  `vector<``int``> constructArray(``int` `N, ``int` `Okay)` `{` `    ` `    ``vector<``int``> A(N, 0);` ` `  `    ` `    ``for` `(``int` `i = 0; i < N; i++) {` `        ``A[i] = i + 1;` `    ``}` ` `  `    ` `    ` `    ` `    ``int` `goal = N - Okay;` ` `  `    ` `    ` `    ``int` `prev = A;` ` `  `    ` `    ` `    ``A = A[target];` ` `  `    ` `    ` `    ` `    ` `    ``for` `(``int` `i = 1; i <= goal; i++) {` `        ``int` `temp = A[i];` `        ``A[i] = prev;` `        ``prev = temp;` `    ``}` ` `  `    ``return` `A;` `}` ` `  `int` `predominant()` `{` `    ``int` `N = 6, Okay = 2;` ` `  `    ` `    ` `    ``vector<``int``> A = constructArray(N, Okay);` ` `  `    ` `    ``for` `(``int` `i = 0; i < N; i++)` `        ``cout << A[i] << ``" "``;` `    ``cout << endl;` `}`

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