Check if Array can be rearranged such that arr[i] XOR arr[i+2] is 0
Given an array arr[] of size N, the task is to check if the array elements can be rearranged in a way such that the bitwise XOR of ith and (i+2)th element is always 0 for any value of i (0 ≤ i < N-2)
Examples:
Input: arr[] = {1, 1, 2, 2}, N = 4
Output: YES
Explanation: Rearrange the array like {1, 2, 1, 2}.
Here XOR of [1, 1] and XOR of [2, 2] is 0.Input: arr[] = {1, 2, 3, 4}, N = 4
Output: NO
Explanation: Here no such arrangement is possible such that arr[i] XOR arr[i+2] is 0.
Naive Approach: The naive approach is to rearrange the array in all possible ways and then for each arrangement check is the given condition is satisfied.
Time Complexity: O(N *N!)
Auxiliary Space: O(N)
Efficient Approach: This problem can be solved on the basis of the following idea:
Bitwise XOR of two elements is 0 only when both the elements are same.
Based on the above observation it can be understood that all the elements in the odd position must be same and all the elements in the even position must be same
So when there is only one unique element (because all elements will be the same) or two unique elements and their frequencies are same as the number of odd and even positions of the array, only then such a rearrangement is possible.
Follow the steps mentioned below to solve the problem.
- Create one unordered_map to count the number of unique elements.
- Traverse the array and store the elements of the array in map.
- Count the number of different types of elements in the map.
- If the count > 2, then its not possible to rearrange the array by alternate position.
- If count = 1, then the arrangement is possible.
- If count = 2, then there are both possibilities:
- If the size of array(N) is even then the frequency of both should be same.
- If the size of array is odd then the frequency of one element should be N/2 and other should be N/2+1.
Below is the implementation of the above approach:
C++14
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to check that rearrangement // possible or not bool find( int n, vector< int > arr) { // Declaring map unordered_map< int , int > m; int count = 0; // Traversing array to check // the number of unique element for ( int i = 0; i < n; i++) { m[arr[i]]++; if (m[arr[i]] == 1) count++; } // Checking the number of different // elements are greater than two or not if (count > 2) { return false ; } else if (count == 0) { return false ; } else { // If all the elements are same if (count == 1) { return true ; } else { // If size is odd if (n % 2) { if (m[arr[0]] == n / 2 || m[arr[0]] == (n / 2) + 1) { return true ; } else return false ; } // If size is even else { if (m[arr[0]] == n / 2) return true ; else return false ; } } } return false ; } // Driver code int main() { // Size of Array int N = 4; vector< int > arr{ 1, 1, 2, 2 }; // Function call bool flag = find(N, arr); if (flag) cout << "YES" ; else cout << "NO" ; return 0; } |
Java
// Java code to implement the approach import java.util.*; class GFG { // Function to check that rearrangement // possible or not static boolean ans = false ; static void find( int n, int [] arr) { // Declaring map HashMap<Integer, Integer> m = new HashMap<>(); int count = 0 ; // Traversing array to check // the number of unique element for ( int i = 0 ; i < n; i++) { if (m.containsKey(arr[i])) m.put(arr[i], m.get(arr[i]) + 1 ); if (m.get(arr[i]) == null )count = count; else count++; } // Checking the number of different // elements are greater than two or not if (count > 2 ) { ans = false ; return ; } else if (count == 0 ) { ans = false ; return ; } else { // If all the elements are same if (count == 1 ) { ans = true ; return ; } else { // If size is odd if (n % 2 == 1 ) { if (m.get(arr[ 0 ]) == n / 2 || m.get(arr[ 0 ]) == (n / 2 ) + 1 ) { ans = true ; return ; } else { ans = false ; return ; } } // If size is even else { if (m.get(arr[ 0 ])== n / 2 ){ ans = true ; return ; } else { ans = false ; return ; } } } } } // Driver code public static void main (String[] args) { int N = 4 ; int arr[] = { 1 , 1 , 2 , 2 }; // Function call find(N, arr); boolean flag = ans; if (!flag) System.out.println( "YES" ); else System.out.println( "NO" ); } } // This code is contributed by hrithikgarg03188. |
Python3
# Python code to implement the approach # Function to check that rearrangement # possible or not def find(n, arr): # Declaring map m = {} count = 0 # Traversing array to check # the number of unique element for i in range ( 0 , n): if m.get(arr[i]) ! = None : m[arr[i]] = m.get(arr[i]) + 1 else : m[arr[i]] = 1 if m[arr[i]] = = 1 : count + = 1 # Checking the number of different # elements are greater than two or not if count > 2 : return False elif count = = 0 : return False else : # If all the elements are same if count = = 1 : return True else : # If size is odd if n % 2 = = 1 : if (m[arr[ 0 ]] = = n / 2 or m[arr[ 0 ]] = = (n / 2 ) + 1 ): return True else : return False # If size is even else : if m[arr[ 0 ]] = = n / 2 : return True else : return False return false # Driver code if __name__ = = "__main__" : # Size of Array N = 4 arr = [ 1 , 1 , 2 , 2 ] # Function call flag = find(N, arr) if flag = = True : print ( "YES" ) else : print ( "NO" ) # This code is contributed by Rohit Pradhan |
C#
// C# code to implement the approach using System; using System.Collections.Generic; public class GFG { // Function to check that rearrangement // possible or not static bool ans = false ; static void find( int n, int [] arr) { // Declaring map Dictionary< int , int > m = new Dictionary< int , int >(); int count = 0; // Traversing array to check // the number of unique element for ( int i = 0; i < n; i++) { if (m.ContainsKey(arr[i])) m[arr[i]] += 1; else m[arr[i]] = 1; count++; } // Checking the number of different // elements are greater than two or not if (count > 2) { ans = false ; return ; } else if (count == 0) { ans = false ; return ; } else { // If all the elements are same if (count == 1) { ans = true ; return ; } else { // If size is odd if (n % 2 == 1) { if ((m[arr[0]] == ( int )(n / 2)) || (m[arr[0]] == ( int )(n / 2) + 1)) { ans = true ; return ; } else { ans = false ; return ; } } // If size is even else { if (m[arr[0]] == ( int )(n / 2)) { ans = true ; return ; } else { ans = false ; return ; } } } } } // Driver code public static void Main( string [] args) { int N = 4; int [] arr = { 1, 1, 2, 2 }; // Function call find(N, arr); bool flag = ans; if (!flag) Console.WriteLine( "YES" ); else Console.WriteLine( "NO" ); } } // This code is contributed by phasing17 |
Javascript
<script> // JavaScript code for the above approach // Function to check that rearrangement // possible or not function find(n, arr) { // Declaring map let m = new Map(); let count = 0; // Traversing array to check // the number of unique element for (let i = 0; i < n; i++) { if (m.has(arr[i])) { m.set(arr[i], m.get(arr[i]) + 1) } else { m.set(arr[i], 1) } if (m.get(arr[i]) == 1) count++; } // Checking the number of different // elements are greater than two or not if (count > 2) { return false ; } else if (count == 0) { return false ; } else { // If all the elements are same if (count == 1) { return true ; } else { // If size is odd if (n % 2) { if (m.get(arr[0]) == Math.floor(n / 2) || m.get(arr[0]) == Math.floor(n / 2) + 1) { return true ; } else return false ; } // If size is even else { if (m.get(arr[0]) == Math.floor(n / 2)) return true ; else return false ; } } } return false ; } // Driver code // Size of Array let N = 4; let arr = [1, 1, 2, 2]; // Function call let flag = find(N, arr); if (flag) document.write( "YES" ); else document.write( "NO" ); // This code is contributed by Potta Lokesh </script> |
YES
Time Complexity: O(N)
Auxiliary Space: O(N)