Minimum elements to be removed to make pairwise Bitwise XOR 0 or 1
Given an array X[] of length N. Then your task is to output the minimum number of elements needed to remove so that the Bitwise XOR of any pair is either 0 or 1.
Examples:
Input: N = 5, X[] = {1, 2, 3, 5, 2}
Output: 2
Explanation: If we remove 1 and 5 from X[] then the remaining elements are {2, 3, 2}. It can be verified that any pair from the remaining X[] will give XOR either 0 or 1.Input: N = 7, X[] = {1, 4, 6, 12, 2, 6, 7}
Output: 4
Explanation: It can be verified that the minimum number of removed elements must be 4.
Approach: Implement the idea below to solve the problem
The problem is based on the observation, we can solve it using the observation of Bitwise concept. For any two numbers A and B, A^B = 1 if and only if A/2 == B/2, So we just checked the maximum numbers that has same value when divided by 2 and subtracted from the length of array.
Steps were taken to solve the problem:
- Initialize a variable let’s say max to store the maximum element.
- Run a loop for finding maximum element and update max variable.
- Initialize an integer array Y[] of size [(max / 2) + 1].
- Update max to -1.
- Run a loop for i = 0 to i < N and follow below mentioned steps under the scope of loop:
- Y[X[i]/2]++
- If (Y[X[i]/2] > max), then max = Y[X[i]/2]
- Output N-max as answer.
Below is the implementation of the above idea:
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; // Function for printing minimum number of // elements needed to remove void Minimum_deletion( int N, vector< int >& X) { // Variable to store max element int max = -1; // Loop for finding max element for ( int i = 0; i < N; i++) { if (X[i] > max) max = X[i]; } // Initialize a vector Y vector< int > Y((max / 2) + 1, 0); max = -1; // Implement the idea discussed // in the Approach section for ( int i = 0; i < N; i++) { Y[X[i] / 2]++; if (Y[X[i] / 2] > max) max = Y[X[i] / 2]; } // Printing the minimum number of // elements needed to remove cout << N - max << endl; } // Driver code int main() { // Inputs int N = 4; vector< int > X = { 1, 2, 2, 5 }; // Function call Minimum_deletion(N, X); return 0; } // This code is contributed by Abhinav Mahajan (abhinav_m22) |
Java
// Java code for the above approach: import java.io.*; class GFG { public static void main(String[] args) { // Inputs int N = 4 ; int [] X = { 1 , 2 , 2 , 5 }; // Function call Minimum_deletion(N, X); } // Method for printing minimum number of // elements needed to remove public static void Minimum_deletion( int N, int X[]) { // Variable to store max element int max = - 1 ; // Loop for finding max element for ( int i = 0 ; i < N; i++) { if (X[i] > max) max = X[i]; } // Initialize an array Y[] int [] Y = new int [(max / 2 ) + 1 ]; max = - 1 ; // Implement the idea discussed // in Approach section for ( int i = 0 ; i < N; i++) { Y[X[i] / 2 ]++; if (Y[X[i] / 2 ] > max) max = Y[X[i] / 2 ]; } // Printing the minimum number of // elements needed to remove System.out.println(N - max); } } |
Python3
def minimum_deletion(N, X): # Variable to store max element maximum = - 1 # Loop for finding the max element for i in range (N): if X[i] > maximum: maximum = X[i] # Initialize a list Y Y = [ 0 ] * ((maximum / / 2 ) + 1 ) maximum = - 1 # Implement the idea discussed # in the Approach section for i in range (N): Y[X[i] / / 2 ] + = 1 if Y[X[i] / / 2 ] > maximum: maximum = Y[X[i] / / 2 ] # Printing the minimum number of # elements needed to remove print (N - maximum) # Driver code if __name__ = = "__main__" : # Inputs N = 4 X = [ 1 , 2 , 2 , 5 ] # Function call minimum_deletion(N, X) |
C#
using System; using System.Collections.Generic; class Geek { // Function for printing minimum number of the // elements needed to remove static void MinimumDeletion( int N, List< int > X) { int max = -1; // Loop for finding the max element foreach ( int num in X) { if (num > max) max = num; } // Initialize a list Y List< int > Y = new List< int >(); for ( int i = 0; i <= max / 2; i++) { Y.Add(0); } max = -1; // Implement the idea discussed in the Approach section foreach ( int num in X) { Y[num / 2]++; if (Y[num / 2] > max) max = Y[num / 2]; } Console.WriteLine(N - max); } // Driver code static void Main( string [] args) { // Inputs int N = 4; List< int > X = new List< int > { 1, 2, 2, 5 }; MinimumDeletion(N, X); } } |
Javascript
Javascript // Javascript code for the above approach // Function for printing minimum number of // elements needed to remove function Minimum_deletion(N, X) { // Variable to store max element let max = -1; // Loop for finding max element for (let i = 0; i < N; i++) { if (X[i] > max) max = X[i]; } // Initialize a vector Y let Y = new Array(Math.trunc(max / 2) + 1).fill(0); max = -1; // Implement the idea discussed // in the Approach section for (let i = 0; i < N; i++) { Y[X[i] / 2]++; if (Y[X[i] / 2] > max) max = Y[X[i] / 2]; } // Printing the minimum number of // elements needed to remove console.log(N - max); } // Driver code // Inputs let N = 4; let X = [1, 2, 2, 5]; // Function call Minimum_deletion(N, X); // This code is contributed by ragul21 |
2
Time Complexity: O(N)
Auxiliary Space: O(N), As another array Y[] is used.