Check if Array elements can be made 0 by Subtracting left adjacent values
Given an array A[] of size N, the task is to check if all the elements of the array, except 1st element can be made 0 by performing the following operation any number of times:
- For any index i, 0 < i < N, make A[i] = A[i] – A[i-1]
Print “YES” or “NO” accordingly.
Examples:
Input: N = 2, A[] = {2, 8, 4}
Output:YES.
Explanation: Choose i = 1, the array becomes {2, 6, 4}
Choose i = 1, the array becomes {2, 4, 4}
Choose i = 2, the array becomes {2, 4, 0}
Choose i = 1, the array becomes {2, 2, 0}
Choose i = 1, the array becomes {2, 0, 0}Input: N = 2, A[] = {3, 4, 2}
Output: NO
Approach:
If first element of the array is a factor of all the remaining elements of the array, then the elements of array can be made 0, because any of them can be converted to have the value same as the first elements. Otherwise, it is not possible.
Follow the given the step to implement the given idea :
- Run a loop from i = 1 to N-1.
- Check if every element has a factor equal to the first element.
- If all the elements of the array have a factor equal to the first element the print YES.
- Otherwise, print NO.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function performing the calculation bool solve( int A[], int N) { bool flag = true ; for ( int i = 1; i < N; i++) { if (A[i] % A[0] != 0) { flag = false ; break ; } } return flag; } // Driver Code int main() { int N = 3; int A[] = { 2, 8, 4 }; // Function call if (solve(A, N)) cout << "YES" << endl; else cout << "NO" << endl; return 0; } |
Java
// Java code to implement the above approach import java.io.*; class GFG { // Function performing the calculation static boolean solve( int [] A, int N) { boolean flag = true ; for ( int i = 1 ; i < N; i++) { if (A[i] % A[ 0 ] != 0 ) { flag = false ; break ; } } return flag; } public static void main(String[] args) { int N = 3 ; int A[] = { 2 , 8 , 4 }; // Function call if (solve(A, N)) { System.out.print( "YES" ); } else { System.out.print( "NO" ); } } } // This code is contributed by lokeshmvs21. |
Python3
# Python code to implement the approach # Function performing the calculation def solve(A, N): flag = True for i in range ( 1 ,N): if (A[i] % A[ 0 ]! = 0 ): flag = False ; break return flag # Driver Code N = 3 A = [ 2 , 8 , 4 ] # Function call if (solve(A, N)): print ( "YES" ) else : print ( "NO" ) # This code is contributed by Atul_kumar_shrivastava. |
C#
// C# code to implement the above approach using System; public class GFG { // Function performing the calculation static bool solve( int [] A, int N) { bool flag = true ; for ( int i = 1; i < N; i++) { if (A[i] % A[0] != 0) { flag = false ; break ; } } return flag; } public static void Main( string [] args) { int N = 3; int []A = { 2, 8, 4 }; // Function call if (solve(A, N)) { Console.WriteLine( "YES" ); } else { Console.WriteLine( "NO" ); } } } // This code is contributed by AnkThon |
Javascript
// JavaScript code to implement the approach // Function performing the calculation function solve(A, N) { let flag = true ; for (let i = 1; i < N; i++) { if (A[i] % A[0] != 0) { flag = false ; break ; } } return flag; } // Driver Code let N = 3; let A = [2, 8, 4 ]; // Function call if (solve(A, N)) console.log( "YES" ); else console.log( "NO" ); // This code is contributed by Ishan Khandelwal |
YES
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us