Given two integers N and K, the task is to construct an array of length N containing exactly K elements divisible 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 divisible by 2
At Position 3, element 2 is not divisible by 3
At Position 4, element 3 is not divisible by 4
At Position 5, element 4 is not divisible 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 divisible 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 N-K 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 6Step 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 6Step 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 6Therefore 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 N-K, there will be K-1 elements left, we will not interfere with these elements. So, we have K-1 elements, which are divisible by their position.
- We will make First element of the array equal to the element at index N-K. This would also be divisible by its position.
- We will make the remaining elements (i.e. from index 1 to N-K) equal to the elements immediate left to them. These all N-K elements will not be divisible by their position then and remaining K elements would be divisible by their position.
Below is the implementation of the above approach:
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Function to construct an array of size// N such that it contains all numbers from// 1 to N and only K elements are divisible by// their position (i.e. index+1)vector<int> constructArray(int N, int K){ // Declaring array of size N vector<int> A(N, 0); // Initializing array as {1, 2, 3....N} for (int i = 0; i < N; i++) { A[i] = i + 1; } // N-K index stored in a variable "target" // After target there will be k-1 elements // which are divisible by their position int target = N - K; // Initializing "prev" variable that helps in // shifting elements to their right int prev = A[0]; // Assigning first element the value at target // index A[0] = A[target]; // Making all elements from index 1 to target // equal to their immediate left element // as any number would not be divisible // by its next number for (int i = 1; i <= target; i++) { int temp = A[i]; A[i] = prev; prev = temp; } return A;}// Driver Codeint main(){ int N = 6, K = 2; // Calling function // to construct the array vector<int> A = constructArray(N, K); // Printing resultant array for (int i = 0; i < N; i++) cout << A[i] << " "; cout << endl;} |
Java
// JAVA program for above approachimport java.util.*;class GFG { // Function to construct an array of size // N such that it contains all numbers from // 1 to N and only K elements are divisible by // their position (i.e. index+1) public static int[] constructArray(int N, int K) { // Declaring array of size N int A[] = new int[N]; for (int i = 0; i < A.length; ++i) { A[i] = 0; } // Initializing array as {1, 2, 3....N} for (int i = 0; i < N; i++) { A[i] = i + 1; } // N-K index stored in a variable "target" // After target there will be k-1 elements // which are divisible by their position int target = N - K; // Initializing "prev" variable that helps in // shifting elements to their right int prev = A[0]; // Assigning first element the value at target // index A[0] = A[target]; // Making all elements from index 1 to target // equal to their immediate left element // as any number would not be divisible // by its next number for (int i = 1; i <= target; i++) { int temp = A[i]; A[i] = prev; prev = temp; } return A; } // Driver Code public static void main(String[] args) { int N = 6, K = 2; // Calling function // to construct the array int A[] = constructArray(N, K); // Printing resultant array for (int i = 0; i < N; i++) System.out.print(A[i] + " "); System.out.println(); }}// This code is contributed by Taranpreet |
Python3
# Python program for above approach# Function to construct an array of size# N such that it contains all numbers from# 1 to N and only K elements are divisible by# their position (i.e. index+1)def constructArray(N, K): # Declaring array of size N A = [0]*N # Initializing array as {1, 2, 3....N} for i in range(N): A[i] = i + 1 # N-K index stored in a variable "target" # After target there will be k-1 elements # which are divisible by their position target = N - K # Initializing "prev" variable that helps in # shifting elements to their right prev = A[0] # Assigning first element the value at target # index A[0] = A[target] # Making all elements from index 1 to target # equal to their immediate left element # as any number would not be divisible # by its next number for i in range(1,target+1): temp = A[i] A[i] = prev prev = temp return A# Driver CodeN = 6K = 2# Calling function# to construct the arrayA = constructArray(N, K)# Printing resultant arrayfor i in range(N): print(A[i],end=" ")# This code is contributed by shinjanpatra |
C#
// C# program for above approachusing System;class GFG { // Function to construct an array of size // N such that it contains all numbers from // 1 to N and only K elements are divisible by // their position (i.e. index+1) static int[] constructArray(int N, int K) { // Declaring array of size N int[] A = new int[N]; for (int i = 0; i < A.Length; ++i) { A[i] = 0; } // Initializing array as {1, 2, 3....N} for (int i = 0; i < N; i++) { A[i] = i + 1; } // N-K index stored in a variable "target" // After target there will be k-1 elements // which are divisible by their position int target = N - K; // Initializing "prev" variable that helps in // shifting elements to their right int prev = A[0]; // Assigning first element the value at target // index A[0] = A[target]; // Making all elements from index 1 to target // equal to their immediate left element // as any number would not be divisible // by its next number for (int i = 1; i <= target; i++) { int temp = A[i]; A[i] = prev; prev = temp; } return A; } // Driver Code public static void Main() { int N = 6, K = 2; // Calling function // to construct the array int[] A = constructArray(N, K); // Printing resultant array for (int i = 0; i < N; i++) Console.Write(A[i] + " "); Console.WriteLine(); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript program for above approach // Function to construct an array of size // N such that it contains all numbers from // 1 to N and only K elements are divisible by // their position (i.e. index+1) const constructArray = (N, K) => { // Declaring array of size N let A = new Array(N).fill(0); // Initializing array as {1, 2, 3....N} for (let i = 0; i < N; i++) { A[i] = i + 1; } // N-K index stored in a variable "target" // After target there will be k-1 elements // which are divisible by their position let target = N - K; // Initializing "prev" variable that helps in // shifting elements to their right let prev = A[0]; // Assigning first element the value at target // index A[0] = A[target]; // Making all elements from index 1 to target // equal to their immediate left element // as any number would not be divisible // by its next number for (let i = 1; i <= target; i++) { let temp = A[i]; A[i] = prev; prev = temp; } return A; } // Driver Code let N = 6, K = 2; // Calling function // to construct the array let A = constructArray(N, K); // Printing resultant array for (let i = 0; i < N; i++) document.write(`${A[i]} `);// This code is contributed by rakeshsahni</script> |
Output
5 1 2 3 4 6
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
