Given 3 integers N, L and R. The task is to construct an array A[] of N integers, such that :
- Each element of the array is in the range [L, R].
- GCD(i, A[i]) are distinct for all elements.
Examples :
Input : N = 5, L = 1, R = 5
Output : {1, 2, 3, 4, 5}
Explanation : It can be seen that each element is in the range [1, 5].
Also, for i = 1, GCD(1, 1)=1, for i = 2, GCD(2, 2) = 2, for i = 3,
GCD(3, 3) = 3, for i = 4, GCD(4, 4) = 4 and for i = 5, GCD(5, 5) = 5.
Hence, all of these are distinct.Input : N = 10, L = 30, R = 35
Output : -1
Explanation : It is not possible to construct an array
satisfying the given conditions.
Approach: The approach of the problem is based on the following observation
To satisfy the given conditions, we will have to assure GCD(i, A[i]) = i, for each index of the array from 1 to N.
The idea is to find the smallest possible element with gcd(i, A[i]) = i, larger than or equal to L for each i, and if that element is smaller than equal to R, then we append it, otherwise we return -1(means not possible).
The problem can be solved by the following approach:
- Iterate from i = 1 to N.
- For each i, find the minimum multiple of i that is strictly greater than L − 1.
- Check if that multiple is less than or equal to R.
- If so, that multiple would be the ith element of the array.
- Else, array construction would not be possible.
Below is the implementation of the above approach:
C++
// C++ code to implement the above approach#include <bits/stdc++.h>using namespace std;// Function to Construct an array whose elements// are in given range and GCD of each element// with its index is distinctvoid constructArray(int N, int L, int R){ // Declaring the array int A[N + 1]; bool flag = true; // Constructing each element of array for (int i = 1; i <= N; i++) { // Creating ith element of the array // as the smallest multiple of i // which is greater than L-1 A[i] = ((L - 1) / i + 1) * i; // Checking if the ith created element // is less than or equal to R if (A[i] > R) { flag = false; break; } } // If flag is false, that implies // it is not possible to construct the array if (flag == false) { cout << -1; } // Else print the constructed array else { for (int i = 1; i <= N; i++) { cout << A[i] << " "; } }}// Driver Codeint main(){ int N = 5, L = 1, R = 5; // Function call constructArray(N, L, R); return 0;} |
Java
// Java code to implement the above approachimport java.io.*;class GFG { // Function to Construct an array whose elements // are in given range and GCD of each element // with its index is distinct public static void constructArray(int N, int L, int R) { // Declaring the array int A[] = new int[N + 1]; boolean flag = true; // Constructing each element of array for (int i = 1; i <= N; i++) { // Creating ith element of the array // as the smallest multiple of i // which is greater than L-1 A[i] = ((L - 1) / i + 1) * i; // Checking if the ith created element // is less than or equal to R if (A[i] > R) { flag = false; break; } } // If flag is false, that implies // it is not possible to construct the array if (flag == false) { System.out.print(-1); } // Else print the constructed array else { for (int i = 1; i <= N; i++) { System.out.print(A[i] + " "); } } } // Driver Code public static void main(String[] args) { int N = 5, L = 1, R = 5; // Function call constructArray(N, L, R); }}// This code is contributed by Rohit Pradhan |
Python3
# Python3 code to implement the above approach# Function to Construct an array whose elements# are in given range and GCD of each element# with its index is distinctdef constructArray(N, L, R) : # Declaring the array A = [0] * (N + 1); flag = True; # Constructing each element of array for i in range(1, N + 1) : # Creating ith element of the array # as the smallest multiple of i # which is greater than L-1 A[i] = ((L - 1) // i + 1) * i; # Checking if the ith created element # is less than or equal to R if (A[i] > R) : flag = False; break; # If flag is false, that implies # it is not possible to construct the array if (flag == False) : print(-1); # Else print the constructed array else : for i in range(1, N + 1) : print(A[i], end=" ");# Driver Codeif __name__ == "__main__" : N = 5; L = 1; R = 5; # Function call constructArray(N, L, R); # This code is contributed by AnkThon |
C#
// C# code to implement the above approachusing System;class GFG{ // Function to Construct an array whose elements // are in given range and GCD of each element // with its index is distinct public static void constructArray(int N, int L, int R) { // Declaring the array int []A = new int[N + 1]; bool flag = true; // Constructing each element of array for (int i = 1; i <= N; i++) { // Creating ith element of the array // as the smallest multiple of i // which is greater than L-1 A[i] = ((L - 1) / i + 1) * i; // Checking if the ith created element // is less than or equal to R if (A[i] > R) { flag = false; break; } } // If flag is false, that implies // it is not possible to construct the array if (flag == false) { Console.Write(-1); } // Else print the constructed array else { for (int i = 1; i <= N; i++) { Console.Write(A[i] + " "); } } } // Driver Code public static void Main(string[] args) { int N = 5, L = 1, R = 5; // Function call constructArray(N, L, R); }}// This code is contributed by AnkThon |
Javascript
<script>// Javascript code to implement the above approach// Function to Construct an array whose elements// are in given range and GCD of each element// with its index is distinctfunction constructArray(N, L, R){ // Declaring the array let A= new Array(N + 1); let flag = true; // Constructing each element of array for (let i = 1; i <= N; i++) { // Creating ith element of the array // as the smallest multiple of i // which is greater than L-1 A[i] = ((L - 1) / i + 1) * i; // Checking if the ith created element // is less than or equal to R if (A[i] > R) { flag = false; break; } } // If flag is false, that implies // it is not possible to construct the array if (flag == false) { document.write(-1); } // Else print the constructed array else { for (let i = 1; i <= N; i++) { document.write(A[i] + " "); } }}// Driver Code let N = 5, L = 1, R = 5; // Function call constructArray(N, L, R); // This code is contributed by satwik4409. </script> |
Output
1 2 3 4 5
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!
Share your thoughts in the comments
