Given a binary matrix. In a single operation, you are allowed to choose two adjacent elements and invert their parity. The operation can be performed any number of times. Write a program to check if all the elements of the array can be converted into a single parity.
Examples:
Input: a[] = {1, 0, 1, 1, 0, 1}
Output: Yes
Invert 2nd and 3rd elements to get {1, 1, 0, 1, 0, 1}
Invert 3rd and 4th elements to get {1, 1, 1, 0, 0, 1}
Invert 4th and 5th elements to get {1, 1, 1, 1, 1, 1}
Input: a[] = {1, 1, 1, 0, 0, 0}
Output: No
Approach: Since only adjacent elements are needed to be flipped, hence the count of parities will give the answer to the question. Only even number of elements are flipped at a time, so if both the parity’s count is odd then it is not possible to make all the parity same else it is possible.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to check if parity// can be made same or notbool flipsPossible(int a[], int n){ int count_odd = 0, count_even = 0; // Iterate and count the parity for (int i = 0; i < n; i++) { // Odd if (a[i] & 1) count_odd++; // Even else count_even++; } // Condition check if (count_odd % 2 && count_even % 2) return false; else return true;}// Drivers codeint main(){ int a[] = { 1, 0, 1, 1, 0, 1 }; int n = sizeof(a) / sizeof(a[0]); if (flipsPossible(a, n)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java implementation of the approach public class GFG { // Function to check if parity // can be made same or not static boolean flipsPossible(int []a, int n) { int count_odd = 0, count_even = 0; // Iterate and count the parity for (int i = 0; i < n; i++) { // Odd if ((a[i] & 1) == 1) count_odd++; // Even else count_even++; } // Condition check if (count_odd % 2 == 1 && count_even % 2 == 1) return false; else return true; } // Drivers code public static void main (String[] args) { int []a = { 1, 0, 1, 1, 0, 1 }; int n = a.length; if (flipsPossible(a, n)) System.out.println("Yes"); else System.out.println("No"); } }// This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the approach # Function to check if parity # can be made same or not def flipsPossible(a, n) : count_odd = 0; count_even = 0; # Iterate and count the parity for i in range(n) : # Odd if (a[i] & 1) : count_odd += 1; # Even else : count_even += 1; # Condition check if (count_odd % 2 and count_even % 2) : return False; else : return True; # Driver Code if __name__ == "__main__" : a = [ 1, 0, 1, 1, 0, 1 ]; n = len(a); if (flipsPossible(a, n)) : print("Yes"); else : print("No"); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approach using System;class GFG { // Function to check if parity // can be made same or not static bool flipsPossible(int []a, int n) { int count_odd = 0, count_even = 0; // Iterate and count the parity for (int i = 0; i < n; i++) { // Odd if ((a[i] & 1) == 1) count_odd++; // Even else count_even++; } // Condition check if (count_odd % 2 == 1 && count_even % 2 == 1) return false; else return true; } // Drivers code public static void Main(String[] args) { int []a = { 1, 0, 1, 1, 0, 1 }; int n = a.Length; if (flipsPossible(a, n)) Console.WriteLine("Yes"); else Console.WriteLine("No"); } }// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript implementation of the approach // Function to check if parity // can be made same or not function flipsPossible(a, n){ let count_odd = 0; let count_even = 0; // Iterate and count the parity for (let i = 0; i < n; i++) { // Odd if ((a[i] & 1) == 1) count_odd++; // Even else count_even++; } // Condition check if (count_odd % 2 == 1 && count_even % 2 == 1) return false; else return true;} // Drivers code let a = [1, 0, 1, 1, 0, 1];let n = a.length; if (flipsPossible(a, n)) document.write("Yes");else document.write("No"); </script> |
Yes
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
