Horje
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>

Output

11 12 12 12 15

Time Complexity: O(N)
Auxiliary Space: O(N), for creating the array of size N.


 


Reffered: https://www.geeksforgeeks.org

Arrays

Related
Minimize moves to segregate even and odd by swapping adjacent elements Minimize moves to segregate even and odd by swapping adjacent elements
Rearrange Array to maximize sum of MEX of all Subarrays starting from first index Rearrange Array to maximize sum of MEX of all Subarrays starting from first index
Maximum Partitions such that any two numbers from two Subsets are co-prime Maximum Partitions such that any two numbers from two Subsets are co-prime
Maximize frequency of an element by adding X to a Subsequence Maximize frequency of an element by adding X to a Subsequence
Check if there is a missing Subsequence of size K in given Array Check if there is a missing Subsequence of size K in given Array

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 13



 

Horje