# Reduce a given Binary Array to a single element by removal of Triplets

Given an binary array **arr[]** cof size **N**, the task is to reduce the array to a single element by the following two operations:

- A triplet of consecutive
**0**‘s or**1**‘s remains unchanged. - A triplet of consecutive array elements consisting of
**two 0’s and a single 1 or vice versa**can be converted to more frequent element.

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

Input:arr[] = {0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1}Output:NoExplanation:

Following are the operations performed on the array:

{0, 1, 1} -> 1 modifies the array to {1, 1, 1, 0, 0, 1, 1, 1, 1}

{1, 0, 0} -> 0 modifies the array to {1, 1, 0, 1, 1, 1, 1}

{1, 0, 1} -> 1 modifies the array to {1, 1, 1, 1, 1}

Since, all the remaining elements are 1, they remain unchanged.

Therefore, the array cannot be reduced to a single element.

Input:arr[] = {1, 0, 0, 0, 1, 1, 1}Output:YesExplanation:

Following are the operations performed on the array:

{1, 0, 0} -> 0 {0, 0, 1, 1, 1}

{0, 0, 1} -> 0 {0, 1, 1}

{0, 1, 1} -> 1 {1}

**Approach: **

Follow the steps below to solve the problem:

- Count the frequency of
**0**‘s and**1**‘s. - Calculate the absolute difference their respective counts.
- If the difference is 1, only then the array can be reduced to 1. Therefore, print Yes.
- Otherwise, print No.

Below is the implementation of the above approach:

## C++

`// C++ program to implement` `// the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to check if it is possible to` `// reduce the array to a single element` `void` `solve(` `int` `arr[], ` `int` `n)` `{` ` ` `// Stores frequency of 0's` ` ` `int` `countzeroes = 0;` ` ` `// Stores frequency of 1's` ` ` `int` `countones = 0;` ` ` `for` `(` `int` `i = 0; i < n; i++) {` ` ` `if` `(arr[i] == 0)` ` ` `countzeroes++;` ` ` `else` ` ` `countones++;` ` ` `}` ` ` `// Condition for array to be reduced` ` ` `if` `(` `abs` `(countzeroes - countones) == 1)` ` ` `cout << ` `"Yes"` `;` ` ` `// Otherwise` ` ` `else` ` ` `cout << ` `"No"` `;` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `arr[] = { 0, 1, 0, 0, 1, 1, 1 };` ` ` `int` `n = ` `sizeof` `(arr) / ` `sizeof` `(arr[0]);` ` ` `solve(arr, n);` ` ` `return` `0;` `}` |

## Java

`// Java program to implement` `// the above approach` `class` `GFG{` `// Function to check if it is possible to` `// reduce the array to a single element` `static` `void` `solve(` `int` `arr[], ` `int` `n)` `{` ` ` ` ` `// Stores frequency of 0's` ` ` `int` `countzeroes = ` `0` `;` ` ` `// Stores frequency of 1's` ` ` `int` `countones = ` `0` `;` ` ` `for` `(` `int` `i = ` `0` `; i < n; i++)` ` ` `{` ` ` `if` `(arr[i] == ` `0` `)` ` ` `countzeroes++;` ` ` `else` ` ` `countones++;` ` ` `}` ` ` `// Condition for array to be reduced` ` ` `if` `(Math.abs(countzeroes - countones) == ` `1` `)` ` ` `System.out.print(` `"Yes"` `);` ` ` `// Otherwise` ` ` `else` ` ` `System.out.print(` `"No"` `);` `}` `// Driver Code` `public` `static` `void` `main(String[] args)` `{` ` ` `int` `arr[] = { ` `0` `, ` `1` `, ` `0` `, ` `0` `, ` `1` `, ` `1` `, ` `1` `};` ` ` `int` `n = arr.length;` ` ` `solve(arr, n);` `}` `}` `// This code is contributed by 29AjayKumar` |

## Python3

`# Python3 program to implement` `# the above approach` `# Function to check if it is possible to` `# reduce the array to a single element` `def` `solve(arr, n):` ` ` `# Stores frequency of 0's` ` ` `countzeroes ` `=` `0` `;` ` ` `# Stores frequency of 1's` ` ` `countones ` `=` `0` `;` ` ` `for` `i ` `in` `range` `(n):` ` ` `if` `(arr[i] ` `=` `=` `0` `):` ` ` `countzeroes ` `+` `=` `1` `;` ` ` `else` `:` ` ` `countones ` `+` `=` `1` `;` ` ` ` ` `# Condition for array to be reduced` ` ` `if` `(` `abs` `(countzeroes ` `-` `countones) ` `=` `=` `1` `):` ` ` `print` `(` `"Yes"` `);` ` ` `# Otherwise` ` ` `else` `:` ` ` `print` `(` `"No"` `);` `# Driver Code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` ` ` `arr ` `=` `[ ` `0` `, ` `1` `, ` `0` `, ` `0` `, ` `1` `, ` `1` `, ` `1` `];` ` ` `n ` `=` `len` `(arr);` ` ` `solve(arr, n);` `# This code is contributed by Amit Katiyar` |

## C#

`// C# program to implement` `// the above approach` `using` `System;` `class` `GFG{` `// Function to check if it is possible to` `// reduce the array to a single element` `static` `void` `solve(` `int` `[]arr, ` `int` `n)` `{` ` ` ` ` `// Stores frequency of 0's` ` ` `int` `countzeroes = 0;` ` ` `// Stores frequency of 1's` ` ` `int` `countones = 0;` ` ` `for` `(` `int` `i = 0; i < n; i++)` ` ` `{` ` ` `if` `(arr[i] == 0)` ` ` `countzeroes++;` ` ` `else` ` ` `countones++;` ` ` `}` ` ` `// Condition for array to be reduced` ` ` `if` `(Math.Abs(countzeroes - countones) == 1)` ` ` `Console.Write(` `"Yes"` `);` ` ` `// Otherwise` ` ` `else` ` ` `Console.Write(` `"No"` `);` `}` `// Driver Code` `public` `static` `void` `Main(String[] args)` `{` ` ` `int` `[]arr = { 0, 1, 0, 0, 1, 1, 1 };` ` ` `int` `n = arr.Length;` ` ` `solve(arr, n);` `}` `}` `// This code is contributed by 29AjayKumar` |

## Javascript

`<script>` `// Javascript program to implement` `// the above approach` `// Function to check if it is possible to` `// reduce the array to a single element` `function` `solve(arr, n)` `{` ` ` ` ` `// Stores frequency of 0's` ` ` `var` `countzeroes = 0;` ` ` `// Stores frequency of 1's` ` ` `var` `countones = 0;` ` ` `for` `(` `var` `i = 0; i < n; i++)` ` ` `{` ` ` `if` `(arr[i] == 0)` ` ` `countzeroes++;` ` ` `else` ` ` `countones++;` ` ` `}` ` ` `// Condition for array to be reduced` ` ` `if` `(Math.abs(countzeroes - countones) == 1)` ` ` `document.write( ` `"Yes"` `);` ` ` `// Otherwise` ` ` `else` ` ` `document.write( ` `"No"` `);` `}` `// Driver Code` `var` `arr = [ 0, 1, 0, 0, 1, 1, 1 ];` `var` `n = arr.length;` `solve(arr, n);` `// This code is contributed by rutvik_56` `</script>` |

**Output:**

Yes

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