Construct an Array such that GCD of each element with their indices is unique
Given two integers L and R, construct an array of given size N such that the GCD (Greatest Common Divisor) of the element with their indices (1-based indexing) is unique for every index. The task is to print the array or output -1 if it is impossible to do so.
Examples:
Input: N = 10, L = 1, R = 15
Output: 1 2 3 4 5 6 7 8 9 10
Explanation: GCD(Arr[i], i) at every index starting from 1 till N is {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} are all distinct.Input: N = 5, L = 11, R = 100
Output: 11 12 12 12 15
Approach: To solve the problem use the following idea:
GCD of any number with their indices at max can be the indices itself so we need to find any multiple in the range L to R for the given number to have distinct set of GCD’s for the whole array
Follow the steps to solve the given problem:
- Initialize an array of size N and create a variable pos initially true to store if an answer exists.
- Iterate the array for all indices from 1 to N (1-based indexing).
- Find the first number greater than L which is divisible by the current index.
- if the number is greater than R update pos to false and terminate the loop.
- else store the number in the array and continue the iteration.
- Print the array as the final output.
Below is the implementation for the above approach:
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; // Driver Code int main() { // Given Input int L = 11, R = 100; int N = 5; // Variable to check if answer exists bool pos = true ; // Initializing an array of size N int arr[N]; for ( int i = 0; i < N; i++) { // Using 1-based indexing int idx = i + 1; // if index is divisible by L if (L % idx == 0) { // L itself is the required number arr[i] = L; } else { // Calculating first number divisible // with index greater than L int first_divisible = ((L / idx) + 1) * idx; // if number exceeds R if (first_divisible > R) { // Updating no answer possible pos = false ; // Terminate the loop break ; } // Store the number in the array arr[i] = first_divisible; } } // if answer exists if (pos) { // Print each element of array for ( int i = 0; i < N; i++) { cout << arr[i] << " " ; } } else { // Print -1 otherwise cout << "-1" << endl; } return 0; } |
Java
// Java code for the above approach import java.io.*; class GFG { // Driver Code public static void main(String[] args) { // Given Input int L = 11 , R = 100 ; int N = 5 ; // Variable to check if answer exists boolean pos = true ; // Initializing an array of size N int arr[] = new int [N]; for ( int i = 0 ; i < N; i++) { // Using 1-based indexing int idx = i + 1 ; // if index is divisible by L if (L % idx == 0 ) { // L itself is the required number arr[i] = L; } else { // Calculating first number divisible // with index greater than L int first_divisible = ((L / idx) + 1 ) * idx; // if number exceeds R if (first_divisible > R) { // Updating no answer possible pos = false ; // Terminate the loop break ; } // Store the number in the array arr[i] = first_divisible; } } // if answer exists if (pos) { // Print each element of array for ( int i = 0 ; i < N; i++) { System.out.print(arr[i] + " " ); } } else { // Print -1 otherwise System.out.println(- 1 ); } } } // This code is contributed by ajaymakvana. |
Python3
# Python3 code for the above approach # Driver Code if __name__ = = "__main__" : # Given Input L = 11 ; R = 100 ; N = 5 ; # Variable to check if answer exists pos = True ; # Initializing an array of size N arr = [ 0 ] * N; for i in range (N) : # Using 1-based indexing idx = i + 1 ; # if index is divisible by L if (L % idx = = 0 ) : # L itself is the required number arr[i] = L; else : # Calculating first number divisible # with index greater than L first_divisible = ((L / / idx) + 1 ) * idx; # if number exceeds R if (first_divisible > R) : # Updating no answer possible pos = False ; # Terminate the loop break ; # Store the number in the array arr[i] = first_divisible; # if answer exists if (pos) : # Print each element of array for i in range (N) : print (arr[i], end = " " ); else : # Print -1 otherwise print ( "-1" ) # This code is contributed by AnkThon |
C#
// C# program for above approach using System; class GFG { // Driver Code public static void Main() { // Given Input int L = 11, R = 100; int N = 5; // Variable to check if answer exists bool pos = true ; // Initializing an array of size N int [] arr = new int [N]; for ( int i = 0; i < N; i++) { // Using 1-based indexing int idx = i + 1; // if index is divisible by L if (L % idx == 0) { // L itself is the required number arr[i] = L; } else { // Calculating first number divisible // with index greater than L int first_divisible = ((L / idx) + 1) * idx; // if number exceeds R if (first_divisible > R) { // Updating no answer possible pos = false ; // Terminate the loop break ; } // Store the number in the array arr[i] = first_divisible; } } // if answer exists if (pos) { // Print each element of array for ( int i = 0; i < N; i++) { Console.Write(arr[i] + " " ); } } else { // Print -1 otherwise Console.Write(-1); } } } // This code is contributed by code_hunt. |
Javascript
<script> // JavaScript code for the above approach // Driver Code // Given Input let L = 11, R = 100; let N = 5; // Variable to check if answer exists let pos = true ; // Initializing an array of size N let arr = new Array(N); for (let i = 0; i < N; i++) { // Using 1-based indexing let idx = i + 1; // if index is divisible by L if (L % idx == 0) { // L itself is the required number arr[i] = L; } else { // Calculating first number divisible // with index greater than L let first_divisible = (Math.floor(L / idx) + 1) * idx; // if number exceeds R if (first_divisible > R) { // Updating no answer possible pos = false ; // Terminate the loop break ; } // Store the number in the array arr[i] = first_divisible; } } // if answer exists if (pos) { // Print each element of array for (let i = 0; i < N; i++) { document.write(arr[i] + " " ); } } else { // Print -1 otherwise document.write(-1); } // This code is contributed by sanjoy_62. </script> |
11 12 12 12 15
Time Complexity: O(N)
Auxiliary Space: O(N), for creating the array of size N.