Given arrays A[] and B[] each of length N and A[i] has all the elements from 1 to N, the task is to check if it is possible to convert A[] to B[] by replacing any pair of A[] with their GCD.
Examples:
Input: N = 2, A[] = {1, 2}, B[] = {1, 1}
Output: YES
Explanation:
First Operation – For A[], choose i = 0 and j = 1. GCD(A[0], A[1]) = GCD(1, 2) = 1. Replace both the elements with GCD = 1. So A[] = {1, 1}.Input: N = 3, A[] = {1, 2, 3}, B[] = {1, 2, 2}
Output: NO
Explanation: It can be verify that it’s not possible to convert A[] to B[] by using given operation.
Approach: Implement the idea below to solve the problem
The problem is observation based and can be solved by calculating GCD of A[i] and B[i] for each index. It should be noted that if B[i]>A[i] at any index, then it is impossible to change A[i] as B[i].
So, This idea gives us approach if GCD(A[i], B[i]) = B[i], Then it is possible to convert A[i] to B[i] at that index, else not possible.
Follow the steps mentioned below to implement the idea:
- Make a boolean variable flag and initialize it to true.
- Run a loop from i = 0 to N-1:
- If GCD(A[i], B[i])=B[i] then continue the loop.
- Else mark the flag as false and break the loop.
- If the flag is true then output YES else NO.
Below is the implementation of the above approach.
C++
// C++ code#include <bits/stdc++.h>using namespace std;// Euclidean algorithm to find GCD(a, b),// where a and b are two input argumentsint GCD(int a, int b){ return b == 0 ? a : GCD(b, a % b);}// Function to check conversionbool conversionChecker(int N, int B[]){ // Flag which will be false if B[i]>A[i] // at any index i bool flag = true; // Loop for traversing on B[] for (int i = 0; i < N; i++) { if (GCD((i + 1), B[i]) == B[i]) { continue; } else { flag = false; break; } } // Returning true/false stored in flag return flag;}int main() { // Testcase 1 int N = 4; // Input array B[], We don't need array A[] // Because it can be achieved by traversing on loop // from 1 to N As A[] is an array of {1, 2, . . ., // N} int B1[] = { 1, 2, 3, 2 }; // Function call for checking if conversion is // possible or not cout<<(conversionChecker(N, B1) ? "YES" : "NO")<<endl; // Testcase 2 N = 5; int B2[] = { 2, 4, 5, 6, 7 }; cout<<(conversionChecker(N, B2) ? "YES" : "NO")<<endl; return 0;}// This code is contributed by ksam24000 |
Java
// Java code to implement the approachimport java.io.*;import java.lang.*;import java.util.*;class GFG { // Driver code public static void main(String[] args) { // Testcase 1 int N = 4; // Input array B[], We don't need array A[] // Because it can be achieved by traversing on loop // from 1 to N As A[] is an array of {1, 2, . . ., // N} int B1[] = { 1, 2, 3, 2 }; // Function call for checking if conversion is // possible or not System.out.println(conversionChecker(N, B1) ? "YES" : "NO"); // Testcase 2 N = 5; int B2[] = { 2, 4, 5, 6, 7 }; System.out.println(conversionChecker(N, B2) ? "YES" : "NO"); ; } // Function to check conversion static boolean conversionChecker(int N, int B[]) { // Flag which will be false if B[i]>A[i] // at any index i boolean flag = true; // Loop for traversing on B[] for (int i = 0; i < N; i++) { if (GCD((i + 1), B[i]) == B[i]) { continue; } else { flag = false; break; } } // Returning true/false stored in flag return flag; } // Euclidean algorithm to find GCD(a, b), // where a and b are two input arguments static int GCD(int a, int b) { return b == 0 ? a : GCD(b, a % b); }} |
Python3
# Python code to implement the approach# Euclidean algorithm to find GCD(a, b),# where a and b are two input argumentsdef GCD(a, b): return a if b == 0 else GCD(b, a % b)# Function to check conversiondef conversionChecker(N, B): # Flag which will be false if B[i]>A[i] # at any index i flag = True # loop for traversing on B[] for i in range(N): if(GCD((i + 1), B[i]) == B[i]): continue else: flag = False break # Returning true/false stored in flag return flag# Testcase 1N = 4# Input array B[], We don't need array A[]# Because it can be achieved by traversing on loop# from 1 to N As A[] is an array of {1, 2, . . .,# N}B1 = [1, 2, 3, 2]# Function call for checking if conversion is# possible or notprint("YES" if conversionChecker(N, B1) else "NO")# Testcase 2N = 5B2 = [2, 4, 5, 6, 7]print("YES" if conversionChecker(N, B2) else "NO")# This code is contributed by lokeshmvs21. |
C#
// C# code to implement the approachusing System;public class GFG { static public void Main() { // Testcase 1 int N = 4; // Input array B[], We don't need array A[] // Because it can be achieved by traversing on loop // from 1 to N As A[] is an array of {1, 2, . . ., // N} int[] B1 = { 1, 2, 3, 2 }; // Function call for checking if conversion is // possible or not Console.WriteLine(conversionChecker(N, B1) ? "YES" : "NO"); // Testcase 2 N = 5; int[] B2 = { 2, 4, 5, 6, 7 }; Console.WriteLine(conversionChecker(N, B2) ? "YES" : "NO"); } // Function to check conversion static bool conversionChecker(int N, int[] B) { // Flag which will be false if B[i]>A[i] // at any index i bool flag = true; // Loop for traversing on B[] for (int i = 0; i < N; i++) { if (GCD((i + 1), B[i]) == B[i]) { continue; } else { flag = false; break; } } // Returning true/false stored in flag return flag; } // Euclidean algorithm to find GCD(a, b), // where a and b are two input arguments static int GCD(int a, int b) { return b == 0 ? a : GCD(b, a % b); }}// This code is contributed by lokesh |
Javascript
// Javascript code// Euclidean algorithm to find GCD(a, b),// where a and b are two input argumentsfunction GCD(a, b){ return b == 0 ? a : GCD(b, a % b);}// Function to check conversionfunction conversionChecker(N, B){ // Flag which will be false if B[i]>A[i] // at any index i let flag = true; // Loop for traversing on B[] for (let i = 0; i < N; i++) { if (GCD((i + 1), B[i]) == B[i]) { continue; } else { flag = false; break; } } // Returning true/false stored in flag return flag;} let N = 4; // Input array B[], We don't need array A[] // Because it can be achieved by traversing on loop // from 1 to N As A[] is an array of {1, 2, . . ., // N} let B1 = [1, 2, 3, 2 ]; // Function call for checking if conversion is // possible or not console.log(conversionChecker(N, B1) ? "YES" : "NO"); // Testcase 2 N = 5; let B2 = [2, 4, 5, 6, 7 ]; console.log(conversionChecker(N, B2) ? "YES" : "NO");// This code is contributed by poojaagarwal2 |
Output
YES NO
Time Complexity: O(N * logM), Where M is the max element of B[].
Auxiliary Space: O(1)
Efficient Approach:
In this approach, We don’t need to calculate GCD at each index, Which will save a little bit of time. For A[i] and B[i], There are 3 possible cases. Which are discussed below:
- If B[i] = A[i]: In such indices, We don’t need to perform the operation, Because A[i] is already equal to B[i].
- If B[i] < A[i]: In this case, A[i] can be converted to B[i] only and only if A[i] % B[i] = 0. Formally B[i] is a perfect divisor of A[i].
- If B[i] > A[i]: In this case, it is impossible to convert A[i] as B[i].
Follow the steps mentioned below to implement the idea:
- Make a boolean variable flag and initialize it to true.
- Run a loop from i = 0 to N-1:
- If A[i] and B[i] are equal, then continue the loop.
- Else if B[i] < A[i], then continue only if B[i] perfectly divides A[i].
- Else mark flag as false and break the loop.
- 3. If flag is true output YES else NO.
Code to implement the approach:
C++
#include <cstring>#include <iostream>using namespace std;// Function to check conversionbool conversionChecker(int N, int B[]){ // Flag which will be false if B[i]>A[i] at any // index i bool flag = true; // Loop for traversing on B[] for (int i = 0; i < N; i++) { // Condition when A[i] is already equal to B[i] if (B[i] == (i + 1)) { continue; } // Condition when B[i] is smaller than A[i] and // A[i] can be converted to B[i] only and only // if A[i]%B[i]==0 else if (B[i] < (i + 1) && (i + 1) % B[i] == 0) { continue; } // Else it will not possible to convert // A[i] to B[i] else { // Marking flag as false flag = false; // Breaking loop break; } } // Returning true/false stored in flag return flag;}// Euclidean algorithm to find GCD(a, b),// where a and b are two input argumentsint GCD(int a, int b) { return b == 0 ? a : GCD(b, a % b); }int main(){ // Testcase 1 int N = 4; // Input array B[], We don't need array A[] // Because it can be achieved by traversing on loop // from 1 to N As A[] is an array of {1, 2 . . . N} int B1[] = { 1, 2, 3, 2 }; // Function call for checking if conversion is // possible or not cout << (conversionChecker(N, B1) ? "YES" : "NO") << endl; // Testcase2 N = 6; int B2[] = { 4, 6, 9, 1, 0, 5 }; // Function call for checking if conversion is // possible or not cout << (conversionChecker(N, B2) ? "YES" : "NO") << endl; return 0;}// This code is contributed by akashish__ |
Java
// Java code to implement the approachimport java.io.*;import java.lang.*;import java.util.*;class GFG { // Driver Function public static void main(String[] args) { // Testcase 1 int N = 4; // Input array B[], We don't need array A[] // Because it can be achieved by traversing on loop // from 1 to N As A[] is an array of {1, 2 . . . N} int B1[] = { 1, 2, 3, 2 }; // Function call for checking if conversion is // possible or not System.out.println(conversionChecker(N, B1) ? "YES" : "NO"); // Testcase2 N = 6; int B2[] = { 4, 6, 9, 1, 0, 5 }; // Function call for checking if conversion is // possible or not System.out.println(conversionChecker(N, B2) ? "YES" : "NO"); } // Function to check conversion static boolean conversionChecker(int N, int B[]) { // Flag which will be false if B[i]>A[i] at any // index i boolean flag = true; // Loop for traversing on B[] for (int i = 0; i < N; i++) { // Condition when A[i] is already equal to B[i] if (B[i] == (i + 1)) { continue; } // Condition when B[i] is smaller than A[i] and // A[i] can be converted to B[i] only and only // if A[i]%B[i]==0 else if (B[i] < (i + 1) && (i + 1) % B[i] == 0) { continue; } // Else it will not possible to convert // A[i] to B[i] else { // Marking flag as false flag = false; // Breaking loop break; } } // Returning true/false stored in flag return flag; } // Euclidean algorithm to find GCD(a, b), // where a and b are two input arguments static int GCD(int a, int b) { return b == 0 ? a : GCD(b, a % b); }} |
Python3
# Python code for the above approach# Function to check conversiondef conversionChecker(N, B): # Flag which will be false if B[i]>A[i] at any # index i flag = True # Loop for traversing on B[] for i in range(N): # Condition when A[i] is already equal to B[i] if B[i] == (i + 1): continue # Condition when B[i] is smaller than A[i] and # A[i] can be converted to B[i] only and only # if A[i]%B[i]==0 elif (B[i] < (i + 1) and (i + 1) % B[i] == 0): continue # Else it will not possible to convert # A[i] to B[i] else: # Marking flag as false flag = False # Breaking loop break # Returning true/false stored in flag return flag# Euclidean algorithm to find GCD(a, b),# where a and b are two input argumentsdef GCD(a, b): return a if b == 0 else GCD(b, a % b)# Testcase 1N = 4# Input array B[], We don't need array A[]# Because it can be achieved by traversing on loop# from 1 to N As A[] is an array of {1, 2 . . . N}B1 = [1, 2, 3, 2]# Function call for checking if conversion is# possible or notif (conversionChecker(N, B1) is True): print("YES")else: print("NO")# Testcase2N = 6;B2 = [4, 6, 9, 1, 0, 5];# Function call for checking if conversion is# possible or notif (conversionChecker(N, B2) is True): print("YES")else: print("NO")# This code is contributed by akashish__ |
C#
// C# code to implement the approachusing System;class GFG { // Driver Function public static void Main(string[] args) { // Testcase 1 int N = 4; // Input array B[], We don't need array A[] // Because it can be achieved by traversing on loop // from 1 to N As A[] is an array of {1, 2 . . . N} int[] B1 = { 1, 2, 3, 2 }; // Function call for checking if conversion is // possible or not Console.WriteLine(conversionChecker(N, B1) ? "YES" : "NO"); // Testcase2 N = 6; int[] B2 = { 4, 6, 9, 1, 0, 5 }; // Function call for checking if conversion is // possible or not Console.WriteLine(conversionChecker(N, B2) ? "YES" : "NO"); } // Function to check conversion static bool conversionChecker(int N, int[] B) { // Flag which will be false if B[i]>A[i] at any // index i bool flag = true; // Loop for traversing on B[] for (int i = 0; i < N; i++) { // Condition when A[i] is already equal to B[i] if (B[i] == (i + 1)) { continue; } // Condition when B[i] is smaller than A[i] and // A[i] can be converted to B[i] only and only // if A[i]%B[i]==0 else if (B[i] < (i + 1) && (i + 1) % B[i] == 0) { continue; } // Else it will not possible to convert // A[i] to B[i] else { // Marking flag as false flag = false; // Breaking loop break; } } // Returning true/false stored in flag return flag; } // Euclidean algorithm to find GCD(a, b), // where a and b are two input arguments static int GCD(int a, int b) { return b == 0 ? a : GCD(b, a % b); }}// This code is contributed by karandeep1234 |
Javascript
// JavaScript code for the above approach // Function to check conversion function conversionChecker(N, B) { // Flag which will be false if B[i]>A[i] at any // index i let flag = true; // Loop for traversing on B[] for (let i = 0; i < N; i++) { // Condition when A[i] is already equal to B[i] if (B[i] == (i + 1)) { continue; } // Condition when B[i] is smaller than A[i] and // A[i] can be converted to B[i] only and only // if A[i]%B[i]==0 else if (B[i] < (i + 1) && (i + 1) % B[i] == 0) { continue; } // Else it will not possible to convert // A[i] to B[i] else { // Marking flag as false flag = false; // Breaking loop break; } } // Returning true/false stored in flag return flag; } // Euclidean algorithm to find GCD(a, b), // where a and b are two input arguments function GCD(a, b) { return b == 0 ? a : GCD(b, a % b); } // Driver Function // Testcase 1 let N = 4; // Input array B[], We don't need array A[] // Because it can be achieved by traversing on loop // from 1 to N As A[] is an array of {1, 2 . . . N} let B1 = [1, 2, 3, 2]; // Function call for checking if conversion is // possible or not console.log(conversionChecker(N, B1) ? "YES" : "NO"); console.log('<br>') // Testcase2 N = 6; let B2 = [4, 6, 9, 1, 0, 5]; // Function call for checking if conversion is // possible or not console.log(conversionChecker(N, B2) ? "YES" : "NO");// This code is contributed by Potta Lokesh |
Output
YES NO
Time Complexity: O(N)
Auxiliary Space: O(1)
Related Articles:
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