Friday, August 19, 2022
HomeSoftware DevelopmentDepend ordered pairs of Array parts such that bitwise AND of Okay...

Depend ordered pairs of Array parts such that bitwise AND of Okay and XOR of the pair is 0

[ad_1]

Enhance Article

Save Article

Like Article

Given an array arr[] of dimension N and an integer Okay, the duty is to search out the depend of all of the ordered pairs (i, j) the place i != j, such that ((arr[i] ⊕ arr[j]) & Okay) = 0. The represents bitwise XOR and & represents bitwise AND.

Examples:

Enter: arr = [1, 2, 3, 4, 5], Okay = 3
Output: 2
Rationalization: There are 2 pairs satisfying the situation. 
These pairs are: (1, 5) and (5, 1)

Enter: arr = [5, 9, 24], Okay = 7
Output: 0
Rationalization: No such pair satisfying the situation exists.

 

Strategy: The given drawback could be solved with the assistance of the next concept:

Utilizing distributive property, we will write ((arr[i] ⊕ arr[j]) & Okay) = ((arr[i] & Okay) ⊕ (arr[j] & Okay))
Since for ((arr[i] & Okay) ⊕ (arr[j] & Okay)) = 0, these two phrases (arr[i] & Okay) and (arr[j] & Okay) should be equal.

Observe the under steps to unravel the issue:

  • Create a map and a solution variable (say Res = 0).
  • Traverse the array and insert (arr[i] & Okay) to map with its depend.
  • Now, traverse the map and for every entry if there are X such occurrences then doable pairs = X*(X-1). So add that to the worth Res.
  • Return Res because the required reply.

Under is the implementation of the above method:

C++

  

#embody <bits/stdc++.h>

utilizing namespace std;

  

int findPair(int* arr, int N, int Okay)

{

    map<int, int> Mp;

    int Res = 0;

  

    for (int i = 0; i < N; i++)

        Mp[arr[i] & Okay]++;

  

    for (auto i : Mp)

        Res += ((i.second - 1) * i.second);

  

    return Res;

}

  

int major()

{

    int arr[] = { 1, 2, 3, 4, 5 };

    int N = sizeof(arr) / sizeof(arr[0]);

    int Okay = 3;

  

    

    cout << findPair(arr, N, Okay) << endl;

    return 0;

}

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

[ad_2]

RELATED ARTICLES

Most Popular

Recent Comments