Monday, August 15, 2022
HomeSoftware DevelopmentReduce insertions in Array to divide it in pairs with Bitwise XOR...

Reduce insertions in Array to divide it in pairs with Bitwise XOR as X

[ad_1]

Given an array arr of size N of distinct numbers and an integer X, the duty is to search out the minimal variety of parts that needs to be added within the array such that the array parts may be grouped in pairs the place the bitwise XOR of every pair is the same as X.

Examples:

 Enter: N = 3, arr[] = {1, 2, 3}, X = 1
Output: 1
Clarification: If we add 0 to the array then the array turns into  {1, 2, 3, 0}. 
This array may be cut up as (1, 0), (2, 3), the place XOR of every pair is 1.

Enter: N = 5, arr[] = {1, 4, 5, 6, 7}, X = 7
Output: 3
Clarification: If we add (2, 0, 3) to the array, it turns into [1, 4, 5, 6, 7, 2, 0, 3]. 
This array may be cut up as (1, 6), (4, 3), (5, 2), (7, 0), with XOR of every pair as 7.

 

Method: The issue may be solved utilizing properties of Bitwise XOR operator:

Based on query, allow us to assume that every pair of Array has bitwise XOR worth as X, i.e.

arr[i] ⊕ arr[j] = X

Since above assertion is true, subsequently beneath assertion may even be true

arr[i] ⊕ X = arr[j]

Primarily based on above relation, we will remedy this downside as following:

  • Discover out current pairs in Array with bitwise XOR worth as X, and ignore them as they wont contribute to the answer.
  • From the remaining parts, the bitwise XOR of every factor with X would be the factor to be added within the Array to fulfill the given constraint.
  • Due to this fact depend of remaining factor would be the required depend of insertions wanted within the Array to separate it into pairs with bitwise XOR as X.

Observe the steps talked about beneath to implement the thought:

  • Create a frequency array to retailer the frequency of the array parts.
  • Insert the primary factor of the array within the hash knowledge construction.
  • Run a loop from i = 1 to N-1
    • Verify if A[i] ⊕ X  is already discovered within the array or not.
    • If not discovered then insert the present factor within the hash knowledge construction.
    • In any other case, decrement the frequency of that factor.
  • Return the whole variety of parts which has not but fashioned a pair.

Beneath is the implementation of the above method.

C++

  

#embrace <bits/stdc++.h>

utilizing namespace std;

  

int minNumbersRequired(int N, int arr[], int X)

{

    

    

    int depend = 0;

  

    

    unordered_map<int, int> freq;

  

    freq[arr[0]]++;

    for (int i = 1; i < N; i++) {

  

        

        

        

        

        if (freq[arr[i] ^ X] > 0) {

            freq[arr[i] ^ X]--;

        }

        else

            freq[arr[i]]++;

    }

  

    

    

    for (auto it = freq.start(); it != freq.finish(); it++)

        depend += it->second;

  

    

    return depend;

}

  

int primary()

{

    int N = 5;

    int arr[] = { 1, 4, 5, 6, 7 };

    int X = 7;

  

    

    cout << minNumbersRequired(N, arr, X);

    return 0;

}

Time Complexity: O(N)
Auxiliary House: O(N)

[ad_2]

RELATED ARTICLES

Most Popular

Recent Comments