# Check if all array elements can be reduced to 0 by repeatedly reducing pairs of consecutive elements by their minimum

Given an array **arr[]** consisting of **N** integers, the task is to check if it is possible to reduce the array elements to **0** by repeatedly subtracting the minimum of any pair of consecutive array elements from both the elements in the pair. If it is possible, then print **“Yes”**. Otherwise, print **“No”**.

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

2, 3, 3, 4, 2Input:arr[] = {}Output:YesExplanation:One of the possible way is:Select the pair of indices (0, 1) and perform the operation, which modifies the array as arr[] = {0, 1, 3, 4, 2}.Select the pair of indices (1, 2), and perform the operation which modifies the array as arr[] = {0, 0, 2, 4, 2}.Select the pair of indices (2, 3), and perform the operation which modifies the array as arr[] = {0, 0, 0, 2, 2}.Select the pair of indices (3, 4), and perform the operation which modifies the array as arr[] = {0, 0, 0, 0, 0}.Therefore, it is possible to convert the array elements to zero. So print “YES”

Input:arr[] = {243, 12, 11}Output:NoExplanation:It is impossible to convert every array elements to zero.

**Approach:** The given problem can be solved based on the following observations:

- Suppose the
**arr[] = {a, b, c, d, e, f},**then it can be observed that a should be lesser than or equal to b i.e.,**a â‰¤ b**to satisfy the above condition. Otherwise, the element**a**will remain greater than**0**. - Now modifying the array as arr[] =
**{0, b – a, c, d, e}**,**b – a**is the leftmost element so the same condition as above applies to it as well i.e.,**b – a â‰¤ c**. - So it can be observed that after repeating the above process in the end, the sum of elements at even indices must equal to the sum of elements at odd indices.

Follow the steps below to solve the problem:

- Traverse the range
**[1, N-1]**and check if**arr[i] < arr[i – 1]**, then print**“NO”**and break. Otherwise, decrement**arr[i]**by**arr[i – 1]**. - After completing the above step, and if none of the above cases satisfies, then check if
**arr[N – 1] = 0**or not. If found to be true, then print**“YES”**. Otherwise, print**“NO”**. - Traverse the given array
**arr[]**over the range**[0, N – 2]**using the variable**i**and perform the following:- If the value of
**arr[i]**is less than**arr[i + 1]**then print**“No”**as all the array elements can’t be reduced to**0**. - Otherwise, decrement
**arr[i + 1]**by**arr[i]**.

- If the value of
- After completing the above steps, if none of the above cases satisfy and the value of
**arr[N – 1]**is**0**, then print**“Yes”**. Otherwise, print**“No”**.

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 it is possible` `// to convert the array` `void` `checkPossible(` `int` `* arr, ` `int` `n)` `{` ` ` `// Traverse the array range [1, N-1]` ` ` `for` `(` `int` `i = 1; i < n; i++) {` ` ` `// If arr[i] < arr[i-1]` ` ` `if` `(arr[i] < arr[i - 1]) {` ` ` `cout << ` `"No\n"` `;` ` ` `return` `;` ` ` `}` ` ` `// Otherwise` ` ` `else` `{` ` ` `// Decrement arr[i] by arr[i-1]` ` ` `arr[i] -= arr[i - 1];` ` ` `arr[i - 1] = 0;` ` ` `}` ` ` `}` ` ` `// If arr[n - 1] is not equal to zero` ` ` `if` `(arr[n - 1] == 0) {` ` ` `cout << ` `"Yes\n"` `;` ` ` `}` ` ` `// Otherwise` ` ` `else` `{` ` ` `cout << ` `"No\n"` `;` ` ` `}` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `arr[] = { 2, 3, 3, 4, 2 };` ` ` `int` `N = ` `sizeof` `(arr) / ` `sizeof` `(arr[0]);` ` ` `// Function Call` ` ` `checkPossible(arr, N);` ` ` `return` `0;` `}` |

## Java

`// Java program to implement` `// the above approach` `import` `java.util.*;` `class` `GFG` `{` `// Function to check if it is possible` `// to convert the array` `static` `void` `checkPossible(` `int` `[] arr, ` `int` `n)` `{` ` ` ` ` `// Traverse the array range [1, N-1]` ` ` `for` `(` `int` `i = ` `1` `; i < n; i++)` ` ` `{` ` ` `// If arr[i] < arr[i-1]` ` ` `if` `(arr[i] < arr[i - ` `1` `])` ` ` `{` ` ` `System.out.print(` `"No\n"` `);` ` ` `return` `;` ` ` `}` ` ` `// Otherwise` ` ` `else` ` ` `{` ` ` `// Decrement arr[i] by arr[i-1]` ` ` `arr[i] -= arr[i - ` `1` `];` ` ` `arr[i - ` `1` `] = ` `0` `;` ` ` `}` ` ` `}` ` ` `// If arr[n - 1] is not equal to zero` ` ` `if` `(arr[n - ` `1` `] == ` `0` `)` ` ` `{` ` ` `System.out.print(` `"Yes\n"` `);` ` ` `}` ` ` `// Otherwise` ` ` `else` ` ` `{` ` ` `System.out.print(` `"No\n"` `);` ` ` `}` `}` `// Driver Code` `public` `static` `void` `main(String args[])` `{` ` ` `int` `arr[] = { ` `2` `, ` `3` `, ` `3` `, ` `4` `, ` `2` `};` ` ` `int` `N = arr.length;` ` ` `// Function Call` ` ` `checkPossible(arr, N);` `}` `}` `// This code is contributed by splevel62.` |

## Python3

`# Python program to implement` `# the above approach` `# Function to check if it is possible` `# to convert the array` `def` `checkPossible(arr, n):` ` ` ` ` `# Traverse the array range [1, N-1]` ` ` `for` `i ` `in` `range` `(` `1` `, n):` ` ` `# If arr[i] < arr[i-1]` ` ` `if` `(arr[i] < arr[i ` `-` `1` `]):` ` ` `print` `(` `"No"` `);` ` ` `return` `;` ` ` `# Otherwise` ` ` `else` `:` ` ` `# Decrement arr[i] by arr[i-1]` ` ` `arr[i] ` `-` `=` `arr[i ` `-` `1` `];` ` ` `arr[i ` `-` `1` `] ` `=` `0` `;` ` ` `# If arr[n - 1] is not equal to zero` ` ` `if` `(arr[n ` `-` `1` `] ` `=` `=` `0` `):` ` ` `print` `(` `"Yes"` `);` ` ` `# Otherwise` ` ` `else` `:` ` ` `print` `(` `"No"` `);` `# Driver Code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` `arr ` `=` `[` `2` `, ` `3` `, ` `3` `, ` `4` `, ` `2` `];` ` ` `N ` `=` `len` `(arr);` ` ` `# Function Call` ` ` `checkPossible(arr, N);` `# This code is contributed by shikhasingrajput` |

## C#

`// C# program to implement` `// the above approach` `using` `System;` `class` `GFG` `{` ` ` `// Function to check if it is possible` `// to convert the array` `static` `void` `checkPossible(` `int` `[] arr, ` `int` `n)` `{` ` ` ` ` `// Traverse the array range [1, N-1]` ` ` `for` `(` `int` `i = 1; i < n; i++)` ` ` `{` ` ` `// If arr[i] < arr[i-1]` ` ` `if` `(arr[i] < arr[i - 1])` ` ` `{` ` ` `Console.Write(` `"No\n"` `);` ` ` `return` `;` ` ` `}` ` ` `// Otherwise` ` ` `else` ` ` `{` ` ` `// Decrement arr[i] by arr[i-1]` ` ` `arr[i] -= arr[i - 1];` ` ` `arr[i - 1] = 0;` ` ` `}` ` ` `}` ` ` `// If arr[n - 1] is not equal to zero` ` ` `if` `(arr[n - 1] == 0)` ` ` `{` ` ` `Console.Write(` `"Yes\n"` `);` ` ` `}` ` ` `// Otherwise` ` ` `else` ` ` `{` ` ` `Console.Write(` `"No\n"` `);` ` ` `}` `}` `// Driver Code` `public` `static` `void` `Main()` `{` ` ` `int` `[] arr = { 2, 3, 3, 4, 2 };` ` ` `int` `N = arr.Length;` ` ` `// Function Call` ` ` `checkPossible(arr, N);` `}` `}` `// This code is contributed by susmitakundugoaldanga` |

## Javascript

`<script>` `// JavaScript program to implement` `// the above approach` ` ` `// Function to check if it is possible` ` ` `// to convert the array` ` ` `function` `checkPossible(arr , n) {` ` ` `// Traverse the array range [1, N-1]` ` ` `for` `(i = 1; i < n; i++) {` ` ` `// If arr[i] < arr[i-1]` ` ` `if` `(arr[i] < arr[i - 1]) {` ` ` `document.write(` `"No\n"` `);` ` ` `return` `;` ` ` `}` ` ` `// Otherwise` ` ` `else` `{` ` ` `// Decrement arr[i] by arr[i-1]` ` ` `arr[i] -= arr[i - 1];` ` ` `arr[i - 1] = 0;` ` ` `}` ` ` `}` ` ` `// If arr[n - 1] is not equal to zero` ` ` `if` `(arr[n - 1] == 0) {` ` ` `document.write(` `"Yes\n"` `);` ` ` `}` ` ` `// Otherwise` ` ` `else` `{` ` ` `document.write(` `"No\n"` `);` ` ` `}` ` ` `}` ` ` `// Driver Code` ` ` ` ` `var` `arr = [ 2, 3, 3, 4, 2 ];` ` ` `var` `N = arr.length;` ` ` `// Function Call` ` ` `checkPossible(arr, N);` `// This code contributed by gauravrajput1` `</script>` |

**Output:**

Yes

**Time Complexity:** O(N)**Auxiliary Space:** O(1)