Given a binary array A[] of size N, the task is to check whether the array can be converted into a palindrome by flipping two bits in each operation.
Note: The operation can be performed any number of times.
Examples:
Input: A[] = {1, 0, 1, 0, 1, 1}
Output: Yes
?Explanation: We can perform the following operation:
Select i = 2 and j = 4. Then {1, 0, 1, 0, 1, 1}?{1, 0, 0, 0, 0, 1} which is a palindrome.Input: A[] = {0, 1}
Output: No
Approach: The problem can be solved based on the following observation:
Count number of 0s and 1s.
- If the value of count of 0s and 1s are odd then no palindrome can be made by performing operation on A[].
- Otherwise, array A[] can converted into a palindrome after performing operation on array.
Follow the below steps to solve the problem:
- Set zeros = 0 and ones = 0 to store the count of number of 0s and 1s in the array.
- After that iterate a loop from 0 to N-1 such as:
- If A[i] = 0 increment the value of zeros otherwise increment the value of ones.
- If the value of zeros and ones is odd then print “No” i.e. it is not possible to convert A to a palindrome by applying the above operation any number of times.
- Otherwise, print “Yes”.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find check whether// array can converted into palindromestring check(int arr[], int n){ int one = 0, zero = 0; for (int i = 0; i < n; i++) { if (arr[i] == '0') { zero++; } else { one++; } } if (one % 2 != 0 && zero % 2 != 0) return "No"; return "Yes";}// Driver Codeint main(){ int A[] = { 1, 0, 1, 0, 1, 1 }; int N = sizeof(A) / sizeof(A[0]); // Function call cout << check(A, N); return 0;}// This code is contributed by aarohirai2616. |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;public class GFG { // Function to find check whether // array can converted into palindrome public static String check(int arr[], int n) { int one = 0, zero = 0; for (int i = 0; i < n; i++) { if (arr[i] == '0') { zero++; } else { one++; } } if (one % 2 != 0 && zero % 2 != 0) return "No"; return "Yes"; } // Driver Code public static void main(String[] args) { int[] A = { 1, 0, 1, 0, 1, 1 }; int N = A.length; // Function Call System.out.println(check(A, N)); }} |
Python3
# Python code to implement the approach# Function to find check whether# array can converted into palindromedef check(arr, n): one = 0 zero = 0 for i in range(0, n): if (arr[i] == '0'): zero = zero + 1 else: one = one + 1 if(one % 2 != 0 & zero % 2 != 0): return "No" return "Yes" # Driver Codeif __name__ == '__main__': A = [1, 0, 1, 0, 1, 1 ] N = len(A) # Function call print(check(A,N)) # This code is contributed by aarohirai2616. |
C#
using System;class GFG { static string check(int[] arr, int n) { int one = 0, zero = 0; for (int i = 0; i < n; i++) { if (arr[i] == '0') { zero++; } else { one++; } } if (one % 2 != 0 && zero % 2 != 0) return "No"; return "Yes"; } static void Main() { int[] A = { 1, 0, 1, 0, 1, 1 }; int N = 6; // Function Call Console.Write(check(A, N)); }}// This code is contributed by garg28harsh. |
Javascript
// JavaScript code to implement the approach// Function to find check whether// array can converted into palindromeconst check = (arr, n) => { let one = 0, zero = 0; for (let i = 0; i < n; i++) { if (arr[i] == '0') { zero++; } else { one++; } } if (one % 2 != 0 && zero % 2 != 0) return "No"; return "Yes";}// Driver Codelet A = [1, 0, 1, 0, 1, 1];let N = A.length;// Function callconsole.log(check(A, N));// This code is contributed by rakeshsahni |
Output
Yes
Time Complexity: O(N)
Auxiliary Space: O(1)
Another Approach:
- Start the program.
- Declare the canBePalindrome() function that takes an integer array arr and its size n as arguments and returns a boolean value.
- Inside the canBePalindrome() function, initialize two integer variables count0 and count1 to 0 to keep the count of 0s and 1s in the array.
- Use a for loop to iterate through each element of the array arr.
- Check if the current element of arr is 0 using the if statement. If it is, increment the value of count0 by 1, else increment the value of count1 by 1.
- After the loop, check if the count of 0s and count of 1s in the array are both even using the boolean expression count0 % 2 == 0 && count1 % 2 == 0. If they are both even, return true, else return false.
- In the main() function, declare an integer array arr and initialize it with the given values.
- Find the size of the array arr using the expression sizeof(arr) / sizeof(arr[0]) and store it in an integer variable n.
- Call the canBePalindrome() function with the array arr and its size n as arguments.
- Use an if-else statement to check if the returned value from canBePalindrome() is true or false. If it is true, print “Yes”, else print “No”.
- End the program.
C++
#include <iostream>using namespace std;bool canBePalindrome(int arr[], int n) { int count0 = 0, count1 = 0; for (int i = 0; i < n; i++) { if (arr[i] == 0) count0++; else count1++; } return (count0 % 2 == 0 && count1 % 2 == 0);}int main() { int arr[] = {1, 0, 1, 0, 1, 1}; int n = sizeof(arr) / sizeof(arr[0]); if (canBePalindrome(arr, n)) cout << "Yes"; else cout << "No"; return 0;} |
Java
import java.io.*;public class Main { public static boolean canBePalindrome(int[] arr) { int count0 = 0, count1 = 0; for (int i = 0; i < arr.length; i++) { if (arr[i] == 0) count0++; else count1++; } return (count0 % 2 == 0 && count1 % 2 == 0); } public static void main(String[] args) { int[] arr = {1, 0, 1, 0, 1, 1}; if (canBePalindrome(arr)) System.out.println("Yes"); else System.out.println("No"); }} |
Python3
# Python3 program for the above approachdef can_be_palindrome(arr): count_0 = 0 count_1 = 0 for num in arr: if num == 0: count_0 += 1 else: count_1 += 1 return count_0 % 2 == 0 and count_1 % 2 == 0# Driver Codearr = [1, 0, 1, 0, 1, 1]n = len(arr)if can_be_palindrome(arr): print("Yes")else: print("No") |
C#
using System;public class Program { public static bool CanBePalindrome(int[] arr, int n) { int count0 = 0, count1 = 0; for (int i = 0; i < n; i++) { if (arr[i] == 0) count0++; else count1++; } return (count0 % 2 == 0 && count1 % 2 == 0); } public static void Main() { int[] arr = {1, 0, 1, 0, 1, 1}; int n = arr.Length; if (CanBePalindrome(arr, n)) Console.WriteLine("Yes"); else Console.WriteLine("No"); }} |
Javascript
function canBePalindrome(arr) { let count0 = 0, count1 = 0; for (let i = 0; i < arr.length; i++) { if (arr[i] === 0) count0++; else count1++; } return (count0 % 2 === 0 && count1 % 2 === 0);}const arr = [1, 0, 1, 0, 1, 1];const result = canBePalindrome(arr);if (result) { console.log("Yes");} else { console.log("No");}//This code is written by Ujjwal Kumar Bhardwaj |
Output
Yes
Time Complexity: O(N)
Auxiliary Complexity: O(1)
Share your thoughts in the comments
