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 <bits/stdc++.h>

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[0];

  

    

    

    A[0] = 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)

By admin

Leave a Reply

Your email address will not be published.