Given an integer N and an array arr[], the task is to check if a sequence of first N natural numbers, i.e. {1, 2, 3, .. N} can be made equal to arr[] by choosing any pair (i, j) from the sequence and replacing both i and j by GCD of i and j. If possible, then print “Yes”. Otherwise, print “No”.
Examples:
Input: N = 4, arr[] = {1, 2, 3, 2}
Output: Yes
Explanation: For the pair (2, 4) in the sequence {1, 2, 3, 4}, GCD(2, 4) = 2. Now, the sequence modifies to {1, 2, 3, 2}, which is same as arr[].Input: N = 3, arr[] = {1, 2, 2}
Output: No
Approach:
We can start by iterating over all pairs of numbers (i, j) such that 1 ? i < j ? N and finding their GCD using the Euclidean algorithm. Then, if we find a pair (i, j) such that GCD(i, j) is equal to arr[i-1] and arr[j-1], we can replace both i and j with GCD(i, j) and continue with the modified sequence. If we are able to modify the sequence to be equal to arr[], then we can print “Yes”. Otherwise, we can print “No”.
Algorithm:
- Initialize a sequence of first N natural numbers, i.e. {1, 2, 3, .. N}.
- Iterate over all pairs of numbers (i, j) such that 1 ? i < j ? N.
- Compute the GCD of i and j using the Euclidean algorithm.
- If GCD(i, j) is equal to arr[i-1] and arr[j-1], replace both i and j with GCD(i, j) in the sequence.
- If the modified sequence is equal to arr[], print “Yes” and return.
- If no such pair (i, j) is found, print “No” and return.
Implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;// Function to compute the GCD using the Euclidean algorithmint gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a);}// Function to check if a sequence of first N natural numbers can be made equal to arr[]void checkSequence(int N, int arr[]) { // Initialize the sequence of first N natural numbers vector<int> seq(N); for (int i = 0; i < N; i++) seq[i] = i+1; // Iterate over all pairs of numbers (i, j) such that 1 ? i < j ? N for (int i = 0; i < N; i++) { for (int j = i+1; j < N; j++) { // Compute the GCD of i and j int g = gcd(seq[i], seq[j]); // If GCD(i, j) is equal to arr[i-1] and arr[j-1], replace both i and j with GCD(i, j) in the sequence if (g == arr[i] && g == arr[j]) { seq[i] = seq[j] = g; break; } } // If the modified sequence is equal to arr[], print "Yes" and return if (seq == vector<int>(arr, arr+N)) { cout << "Yes\n"; return; } } // If no such pair (i, j) is found, print "No" and return cout << "No\n";}// Driver codeint main() { int N = 4; int arr[] = {1, 2, 3, 2}; checkSequence(N, arr); return 0;} |
Java
import java.util.*;public class Main { // Function to compute the GCD using the Euclidean // algorithm public static int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a); } // Function to check if a sequence of first N natural // numbers can be made equal to arr[] public static void checkSequence(int N, int[] arr) { // Initialize the sequence of first N natural // numbers List<Integer> seq = new ArrayList<>(); for (int i = 0; i < N; i++) seq.add(i + 1); // Iterate over all pairs of numbers (i, j) such // that 1 ? i < j ? N for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { // Compute the GCD of i and j int g = gcd(seq.get(i), seq.get(j)); // If GCD(i, j) is equal to arr[i-1] and // arr[j-1], replace both i and j with // GCD(i, j) in the sequence if (g == arr[i] && g == arr[j]) { seq.set(i, g); seq.set(j, g); break; } } // If the modified sequence is equal to arr[], // print "Yes" and return if (seq.equals(Arrays.asList( Arrays.stream(arr).boxed().toArray( Integer[] ::new)))) { System.out.println("Yes"); return; } } // If no such pair (i, j) is found, print "No" and // return System.out.println("No"); } // Driver code public static void main(String[] args) { int N = 4; int[] arr = { 1, 2, 3, 2 }; checkSequence(N, arr); }}// Contributed by sdeadityasharma |
Python3
from typing import Listimport math# Function to compute the GCD using the Euclidean algorithmdef gcd(a: int, b: int) -> int: if a == 0: return b return gcd(b % a, a)# Function to check if a sequence of first N natural# numbers can be made equal to arr[]def checkSequence(N: int, arr: List[int]): # Initialize the sequence of first N natural numbers seq = list(range(1, N+1)) # Iterate over all pairs of numbers (i, j) such that 1 ? i < j ? N for i in range(N): for j in range(i+1, N): # Compute the GCD of i and j g = gcd(seq[i], seq[j]) # If GCD(i, j) is equal to arr[i-1] and arr[j-1], replace both i and j with # GCD(i, j) in the sequence if g == arr[i] and g == arr[j]: seq[i] = g seq[j] = g break # If the modified sequence is equal to arr[], print "Yes" and return if seq == list(range(1, N+1)): print("Yes") return # If no such pair (i, j) is found, print "No" and return print("No")# Driver codeif __name__ == '__main__': N = 4 arr = [1, 2, 3, 2] checkSequence(N, arr) |
C#
// C# Program for the above approachusing System;using System.Collections.Generic;using System.Linq;class MainClass { // Function to compute the GCD using the Euclidean // algorithm public static int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a); } // Function to check if a sequence of first N natural // numbers can be made equal to arr[] public static void checkSequence(int N, int[] arr) { // Initialize the sequence of first N natural // numbers List<int> seq = new List<int>(); for (int i = 0; i < N; i++) seq.Add(i + 1); // Iterate over all pairs of numbers (i, j) such // that 1 ? i < j ? N for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { // Compute the GCD of i and j int g = gcd(seq[i], seq[j]); // If GCD(i, j) is equal to arr[i-1] and // arr[j-1], replace both i and j with // GCD(i, j) in the sequence if (g == arr[i] && g == arr[j]) { seq[i] = g; seq[j] = g; break; } } // If the modified sequence is equal to arr[], // print "Yes" and return if (seq.SequenceEqual(arr)) { Console.WriteLine("Yes"); return; } } // If no such pair (i, j) is found, print "No" and // return Console.WriteLine("No"); } // Driver code public static void Main(string[] args) { int N = 4; int[] arr = { 1, 2, 3, 2 }; checkSequence(N, arr); }}// This code is contributed by Prince Kumar |
Javascript
// Function to compute the GCD using the Euclidean algorithmfunction gcd(a, b) { if (a === 0) { return b; } return gcd(b % a, a);}// Function to check if a sequence of first N natural// numbers can be made equal to arr[]function checkSequence(N, arr) { // Initialize the sequence of first N natural numbers const seq = Array.from({ length: N }, (_, i) => i + 1); // Iterate over all pairs of numbers (i, j) such that 1 ? i < j ? N for (let i = 0; i < N; i++) { for (let j = i + 1; j < N; j++) { // Compute the GCD of i and j const g = gcd(seq[i], seq[j]); // If GCD(i, j) is equal to arr[i-1] and arr[j-1], replace both i and j with // GCD(i, j) in the sequence if (g === arr[i] && g === arr[j]) { seq[i] = g; seq[j] = g; break; } } // If the modified sequence is equal to arr[], print "Yes" and return if (seq.every((value, index) => value === index + 1)) { console.log("Yes"); return; } } // If no such pair (i, j) is found, print "No" and return console.log("No");}// Driver codeconst N = 4;const arr = [1, 2, 3, 2];checkSequence(N, arr); |
Output
Yes
Time Complexity: O(N * sqrt(N) * log(N))
Space Complexity: O(N)
Approach: The idea is based on the fact that the GCD of two numbers lies between 1 and the minimum of the two numbers. By definition of gcd, it’s the greatest number that divides both. Therefore, make the number at an index smaller if and only if there exists some number which is its factor. Hence, it can be concluded that for every ith index in the array, if the follow condition holds true, the array arr[] can be obtained from the sequence of first N natural numbers.
(i + 1) % arr[i] == 0
Follow the steps below to solve the problem:
- Traverse the array arr[] using variable i.
- For every ith index, check if (i + 1) % arr[i] is equal to 0 or not. If found to be false for any array element, print “No”.
- Otherwise, after complete traversal of the array, print “Yes”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if array arr[]// can be obtained from first N// natural numbers or notvoid isSequenceValid(vector<int>& B, int N){ for (int i = 0; i < N; i++) { if ((i + 1) % B[i] != 0) { cout << "No"; return; } } cout << "Yes";}// Driver Codeint main(){ int N = 4; vector<int> arr{ 1, 2, 3, 2 }; // Function Call isSequenceValid(arr, N); return 0;} |
Java
// Java program for the above approach class GFG{ // Function to check if array arr[]// can be obtained from first N// natural numbers or notstatic void isSequenceValid(int[] B, int N){ for(int i = 0; i < N; i++) { if ((i + 1) % B[i] != 0) { System.out.print("No"); return; } } System.out.print("Yes");} // Driver codepublic static void main(String[] args){ int N = 4; int[] arr = { 1, 2, 3, 2 }; // Function Call isSequenceValid(arr, N); }} // This code is contributed by sanjoy_62 |
Python3
# Python3 program for the above approach # Function to check if array arr[]# can be obtained from first N# natural numbers or notdef isSequenceValid(B, N): for i in range(N): if ((i + 1) % B[i] != 0): print("No") return print("Yes") # Driver CodeN = 4arr = [ 1, 2, 3, 2 ] # Function CallisSequenceValid(arr, N)# This code is contributed by susmitakundugoaldanga |
C#
// C# program for the above approach using System;class GFG{ // Function to check if array arr[]// can be obtained from first N// natural numbers or notstatic void isSequenceValid(int[] B, int N){ for(int i = 0; i < N; i++) { if ((i + 1) % B[i] != 0) { Console.WriteLine("No"); return; } } Console.WriteLine("Yes");} // Driver codepublic static void Main(){ int N = 4; int[] arr = { 1, 2, 3, 2 }; // Function Call isSequenceValid(arr, N); }}// This code is contributed by code_hunt |
Javascript
<script>// Javascript program to implement// the above approach// Function to check if array arr[]// can be obtained from first N// natural numbers or notfunction isSequenceValid(B, N){ for(let i = 0; i < N; i++) { if ((i + 1) % B[i] != 0) { document.write("No"); return; } } document.write("Yes");}// Driver code let N = 4; let arr = [ 1, 2, 3, 2 ]; // Function Call isSequenceValid(arr, N); // This code is contributed by souravghosh0416.</script> |
Output:
Yes
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
