Check if Binary Array can be made palindrome after K bitwise XOR with 1
Given a binary array arr[] of size N and an integer K, the task is to check whether the binary array can be turned into a palindrome after K number of operations where in one operation, any random index can be chosen and the value stored in the index will be replaced by its bitwise XOR(^) with1.
Examples:
Input: arr[] = { 1, 0, 0, 1, 1}, K = 0
Output: No
Explanation: As the array is not a palindrome, we must need some non-zero number of operations
to make it palindrome.Input: arr[] = { 1, 0, 1, 1, 0, 0}, K = 1
Output: Yes
Explanation: Closest arrays which are palindrome : {0, 0, 1, 1, 0, 0} and {1, 0, 1, 1, 0, 1}, which is possible
using 1 such operations only.
Approach: The approach to solve the problem is based on the following idea:
The minimum number of operations required is the number of unequal elements equidistant from the mid of the array and to make them equal it takes 1 operation (from 1 to 0 or from 0 to 1).
There is need of 2 operations to change two equal elements and make them have the same value again using bitwise XOR.
To implement this idea, follow the steps shown below :
- Initialize two pointers pointing at the two ends of the array.
- Find the number of unequal array elements while traversing the array from its two ends.
- If the number is greater than K, then it is impossible to reach the target with exactly K steps.
- If the number is exactly equal to K, then it is possible to make the array palindrome.
- Otherwise, if the number is lesser than K:
- If the array length is odd, then any number of positive K is fine as we can perform the operations at the mid index.
- If the array length is even, to keep it a palindrome, we must choose two indices and make the operations on those indices. So remaining K has to be even.
Here is the code for the above approach:
C++
// C++ code for the approach #include <bits/stdc++.h> using namespace std; // Function to check whether the array // can be turned into palindrome after K // number of operations bool check_possibility( int * arr, int K) { // Store the length of the array in // arr_length variable int arr_length = sizeof (arr) / sizeof ( arr[0]); // Initialize two pointers from left and // right ends of the array int i = 0; int j = arr_length - 1; // Keep iterating through the array from // two ends until the two pointers cross // each other to count the number // of the different array items. while (i < j) { // If the two elements are unequal, // decrease the value of K by one if (arr[i] != arr[j]) { K--; } // Move the left pointer towards the // right and right pointer towards the // left i++; j--; } // The unequal items are more than K or K // becomes less than zero, it is impossible // to make it a palindrome with D operations. if (K < 0) { return false ; } // If K has a non-negative value, we make the // array a palindrome if it has an odd length // the remaining value of K is odd as we have // to choose two indices at a time to keep it // as a palindrome. else { if ((arr_length % 2) != 0 || (K % 2) == 0) { return true ; } else { return false ; } } } // Driver code int main() { int arr[6] = { 1, 0, 1, 1, 0, 0 }; int K = 1; // Function call if (check_possibility(arr, K) == true ) { cout << "Yes" << endl; } else { cout << "No" << endl; } return 0; } |
Java
// Java code for the approach import java.io.*; class GFG { // Function to check whether the array // can be turned into palindrome after K // number of operations public static boolean check_possibility( int arr[], int K) { // Store the length of the array in // arr_length variable int arr_length = arr.length; // Initialize two pointers from left and // right ends of the array int i = 0 ; int j = arr_length - 1 ; // Keep iterating through the array from // two ends until the two pointers cross // each other to count the number // of the different array items. while (i < j) { // If the two elements are unequal, // decrease the value of K by one if (arr[i] != arr[j]) { K--; } // Move the left pointer towards the // right and right pointer towards the // left i++; j--; } // The unequal items are more than K or K // becomes less than zero, it is impossible // to make it a palindrome with D operations. if (K < 0 ) { return false ; } // If K has a non-negative value, we make the // array a palindrome if it has an odd length // the remaining value of K is odd as we have // to choose two indices at a time to keep it // as a palindrome. else { if ((arr_length % 2 ) != 0 || (K % 2 ) == 0 ) { return true ; } else { return false ; } } } public static void main(String[] args) { int arr[] = { 1 , 0 , 1 , 1 , 0 , 0 }; int K = 1 ; // Function call if (check_possibility(arr, K) == true ) { System.out.println( "Yes" ); } else { System.out.println( "No" ); } } } // This code is contributed by Rohit Pradhan |
C#
// C# code for the approach using System; class GFG { // Function to check whether the array // can be turned into palindrome after K // number of operations static bool check_possibility( int [] arr, int K) { // Store the length of the array in // arr_length variable int arr_length = arr.Length; // Initialize two pointers from left and // right ends of the array int i = 0; int j = arr_length - 1; // Keep iterating through the array from // two ends until the two pointers cross // each other to count the number // of the different array items. while (i < j) { // If the two elements are unequal, // decrease the value of K by one if (arr[i] != arr[j]) { K--; } // Move the left pointer towards the // right and right pointer towards the // left i++; j--; } // The unequal items are more than K or K // becomes less than zero, it is impossible // to make it a palindrome with D operations. if (K < 0) { return false ; } // If K has a non-negative value, we make the // array a palindrome if it has an odd length // the remaining value of K is odd as we have // to choose two indices at a time to keep it // as a palindrome. else { if ((arr_length % 2) != 0 || (K % 2) == 0) { return true ; } else { return false ; } } } public static int Main() { int [] arr = new int [] { 1, 0, 1, 1, 0, 0 }; int K = 1; // Function call if (check_possibility(arr, K) == true ) { Console.WriteLine( "Yes" ); } else { Console.WriteLine( "No" ); } return 0; } } // This code is contributed by Taranpreet |
Python3
# Python code for the approach def check_possibility(arr, K): # Store the length of the array in # arr_length variable arr_length = len (arr) # Initialize two pointers from left and right # ends of the array i = 0 j = arr_length - 1 # Keep iterating through the array from two # ends until the two pointers cross each # other to count the number of the different # array items. while (i < j): # If the two elements are unequal, # decrease the value of K by one if (arr[i] ! = arr[j]): K - = 1 # Move the left pointer towards the right # and right pointer towards the left i + = 1 j - = 1 # The unequal items are more than K or # K becomes less than zero, it is impossible # to make it a palindrome with K operations. if (K < 0 ): return False # If K has a non-negative value, we make the # array a palindrome if it has an odd length # the remaining value of K is odd as we have # to choose two indices at a time # to keep it as a palindrome else : if ( (arr_length % 2 )! = 0 or (K % 2 ) = = 0 ): return True else : return False # Driver code if __name__ = = '__main__' : arr = [ 1 , 0 , 1 , 1 , 0 , 0 ] K = 1 if check_possibility(arr, K) = = True : print ( "Yes" ) else : print ( "No" ) |
Javascript
// JavaScript code for the approach // Function to check whether the array // can be turned into palindrome after K // number of operations function check_possibility(arr, K) { // Store the length of the array in // arr_length variable var arr_length = arr.length; // Initialize two pointers from left and // right ends of the array var i = 0; var j = arr_length - 1; // Keep iterating through the array from // two ends until the two pointers cross // each other to count the number // of the different array items. while (i < j) { // If the two elements are unequal, // decrease the value of K by one if (arr[i] != arr[j]) { K--; } // Move the left pointer towards the // right and right pointer towards the // left i++; j--; } // The unequal items are more than K or K // becomes less than zero, it is impossible // to make it a palindrome with D operations. if (K < 0) { return false ; } // If K has a non-negative value, we make the // array a palindrome if it has an odd length // the remaining value of K is odd as we have // to choose two indices at a time to keep it // as a palindrome. else { if ((arr_length % 2) != 0 || (K % 2) == 0) { return true ; } else { return false ; } } } // Driver code var arr = [ 1, 0, 1, 1, 0, 0 ]; var K = 1; // Function call if (check_possibility(arr, K) == true ) { console.log( "Yes" ); } else { console.log( "No" ); } // This code is contributed by phasing17 |
Yes
Time Complexity: O(N)
Auxiliary Space: O(1)