Given a sequence of non-negative integers, say a1, a2, …, an. Only following actions can be performed on the given sequence:
- Subtract 1 from a[i] and a[i+1] both.
Find if the series can be modified into all zeros using any required number of above operations.
Examples :
Input : 1 2 Output : NO Explanation: Only two elements, if we subtract 1 then it will convert into [0, 1]. so answer is NO. Input : 0 1 1 0 Output : YES Explanation: Here we can choose both 1 and subtract 1 from them then array becomes [0, 0, 0, 0]. So answer is YES. Input : 1 2 3 4 Output : NO Explanation: if we try to subtract 1 any number of times then array will be [0, 0, 0, 1]. [1, 2, 3, 4]->[0, 1, 3, 4]->[0, 0, 2, 3]-> [0, 0, 1, 2]->[0, 0, 0, 1].
Approach 1 :
If all adjacent elements(i, i+1) in array are equal and total number of element in array is even then it’s all element can be converted to zero. For example, if array elements are like {1, 1, 2, 2, 3, 3} then its all element is convertible into zero.
Then in this case sum of every odd positioned value are always equal to the sum of even positioned value.
Implementation:
C++
// CPP program to find if it is possible// to make all array elements 0 by decrement// operations.#include <bits/stdc++.h>using namespace std;bool isPossibleToZero(int a[], int n){ // used for storing the sum of even // and odd position element in array. int even = 0, odd = 0; for (int i = 0; i < n; i++) { // if position is odd, store sum // value of odd position in odd if (i & 1) odd += a[i]; // if position is even, store sum // value of even position in even else even += a[i]; } return (odd == even);}// Driver programint main(){ int arr[] = { 0, 1, 1, 0 }; int n = sizeof(arr) / sizeof(arr[0]); if (isPossibleToZero(arr, n)) cout << "YES"; else cout << "NO";} |
Java
// Java program to find if// it is possible to make // all array elements 0 by// decrement operations.import java.io.*;class GFG { static boolean isPossibleToZero(int a[], int n){ // used for storing the // sum of even and odd // position element in array. int even = 0, odd = 0; for (int i = 0; i < n; i++) { // if position is odd, // store sum value of // odd position in odd if ((i & 1) == 0) odd += a[i]; // if position is even, // store sum value of // even position in even else even += a[i]; } return (odd == even);}// Driver Codepublic static void main(String[] args) { int arr[] = { 0, 1, 1, 0 }; int n = arr.length; if (isPossibleToZero(arr, n)) System.out.println("YES"); else System.out.println("NO");}}// This code is contributed by m_kit |
Python3
# Python3 program to find if it is # possible to make all array elements# 0 by decrement operations.def isPossibleToZero(a, n): # used for storing the # sum of even and odd # position element in array. even = 0; odd = 0; for i in range(n): # if position is odd, store sum # value of odd position in odd if (i & 1): odd += a[i]; # if position is even, store sum # value of even position in even else: even += a[i]; return (odd == even);# Driver Codearr = [0, 1, 1, 0];n = len(arr);if (isPossibleToZero(arr, n)): print("YES");else: print("NO");# This code is contributed by mits |
C#
// C# program to find if// it is possible to make // all array elements 0 by// decrement operations.using System;class GFG{static bool isPossibleToZero(int []a, int n){ // used for storing the // sum of even and odd // position element in array. int even = 0, odd = 0; for (int i = 0; i < n; i++) { // if position is odd, // store sum value of // odd position in odd if ((i & 1) == 0) odd += a[i]; // if position is even, // store sum value of // even position in even else even += a[i]; } return (odd == even);}// Driver Codestatic public void Main (){ int []arr = {0, 1, 1, 0}; int n = arr.Length; if (isPossibleToZero(arr, n)) Console.WriteLine("YES"); else Console.WriteLine("NO");}}// This code is contributed// by m_kit |
PHP
<?php// PHP program to find if it // is possible to make all// array elements 0 by // decrement operations.function isPossibleToZero($a, $n){ // used for storing the // sum of even and odd // position element in array. $even = 0; $odd = 0; for ($i = 0; $i < $n; $i++) { // if position is odd, // store sum value of // odd position in odd if ($i & 1) $odd += $a[$i]; // if position is even, // store sum value of // even position in even else $even += $a[$i]; } return ($odd == $even);}// Driver Code$arr = array (0, 1, 1, 0);$n = sizeof($arr);if (isPossibleToZero($arr, $n)) echo "YES";else echo "NO";// This code is contributed by ajit?> |
Javascript
<script>// Javascript program to find if// it is possible to make // all array elements 0 by// decrement operations.function isPossibleToZero(a, n){ // Used for storing the // sum of even and odd // position element in array. let even = 0, odd = 0; for(let i = 0; i < n; i++) { // If position is odd, // store sum value of // odd position in odd if ((i & 1) == 0) odd += a[i]; // If position is even, // store sum value of // even position in even else even += a[i]; } return (odd == even);}// Driver codelet arr = [ 0, 1, 1, 0 ];let n = arr.length;if (isPossibleToZero(arr, n)) document.write("YES");else document.write("NO"); // This code is contributed by mukesh07</script> |
Output:
YES
Approach 2: If Number formed by given array element is divisible by 11 then all elements of array also can be convertible to zero.
For ex: given array {0, 1, 1, 0}, number formed by this array is 110 then it is divisible by 11. So all elements can be converted into zero.
Implementation:
C++
// CPP implementation of the // above approach#include <bits/stdc++.h>using namespace std;bool isPossibleToZero(int a[], int n){ // converting array element into number int num = 0; for (int i = 0; i < n; i++) num = num * 10 + a[i]; // Check if divisible by 11 return (num % 11 == 0);}// Driver programint main(){ int arr[] = { 0, 1, 1, 0 }; int n = sizeof(arr) / sizeof(arr[0]); if (isPossibleToZero(arr, n)) cout << "YES"; else cout << "NO";} |
Java
// Java implementation of the above approachimport java.io.*;class GFG { static boolean isPossibleToZero(int a[], int n) { // converting array element into number int num = 0; for (int i = 0; i < n; i++) num = num * 10 + a[i]; // Check if divisible by 11 return (num % 11 == 0); } // Driver program public static void main (String[] args) { int arr[] = {0, 1, 1, 0}; int n = arr.length; if (isPossibleToZero(arr, n)) System.out.println( "YES"); else System.out.println ("NO"); }}// This code is contributed by @ajit |
Python3
# Python3 implementation of the # above approachdef isPossibleToZero(a, n): # converting array element # into number num = 0; for i in range(n): num = num * 10 + a[i]; # Check if divisible by 11 return (num % 11 == 0);# Driver Codearr = [ 0, 1, 1, 0 ];n = len(arr);if (isPossibleToZero(arr, n)): print("YES");else: print("NO");# This code is contributed mits |
C#
// C# implementation of the above approachusing System;class GFG { static bool isPossibleToZero(int[] a, int n){ // converting array element into number int num = 0; for (int i = 0; i < n; i++) num = num * 10 + a[i]; // Check if divisible by 11 return (num % 11 == 0);}// Driver Codepublic static void Main(){ int[] arr = {0, 1, 1, 0}; int n = arr.Length; if (isPossibleToZero(arr, n)) Console.WriteLine("YES"); else Console.WriteLine("NO");}}// This code is contributed // by Akanksha Rai |
PHP
<?php// PHP implementation of // the above approachfunction isPossibleToZero($a, $n){ // converting array // element into number $num = 0; for ($i = 0; $i < $n; $i++) $num = $num * 10 + $a[$i]; // Check if divisible by 11 return ($num % 11 == 0);}// Driver Code$arr = array( 0, 1, 1, 0 );$n = sizeof($arr);if (isPossibleToZero($arr, $n)) echo "YES";else echo "NO";// This code is contributed ajit?> |
Javascript
<script>// Javascript implementation of the above approachfunction isPossibleToZero(a, n){ // Converting array element into number let num = 0; for(let i = 0; i < n; i++) num = num * 10 + a[i]; // Check if divisible by 11 return (num % 11 == 0);}// Driver codelet arr = [ 0, 1, 1, 0 ];let n = arr.length;if (isPossibleToZero(arr, n)) document.write("YES");else document.write("NO"); // This code is contributed by divyeshrabadiya07</script> |
Output:
YES
The above implementation causes overflow for slightly bigger arrays. We can use below method to avoid overflow.Check if a large number is divisible by 11 or not
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!
