Friday, March 25, 2022
HomeSoftware DevelopmentRely of pairs with bitwise XOR worth larger than its bitwise AND...

Rely of pairs with bitwise XOR worth larger than its bitwise AND worth | Set 2


Given an array arr that comprises N constructive Integers. Discover the rely of all attainable pairs whose bit smart XOR worth is larger than bit smart AND worth

Examples:

Enter : arr[]={ 12, 4 , 15}
Output:  2
Clarification: 12 ^ 4 = 8 ,  12 & 4 = 4 . so 12 ^ 4 > 12 & 4
                       4 ^ 15 = 11,   4 & 15 = 4. so 4 ^ 15  > 4 & 15 . 
So , above two are legitimate pairs { 12,4 } ,{4, 15}  .

Enter:  arr[] ={ 1, 1, 3, 3 }
Output: 4

 

Naive Method: For the brute drive method to resolve this drawback, please seek advice from the SET 1 of this text.

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

Environment friendly Method: The environment friendly method to resolve this drawback relies on following commentary:

Statement: 

The commentary is that if the index of  MSB ( Most Vital bit, also referred to as leftmost set bit), of any two parts is similar then it’s assured that the bitwise XOR of these two parts is lower than their bitwise AND ., as a result of 1^1=0, it is going to unset the MSB.  whereas 1&1=1, MSB will stay set.

Illustration:

If a = 1010, b = 1000,

Then a & b= 1000 and a ^ b = 0010

So if the MSB index is similar in each then their bitwise XOR will at all times be lower than bitwise AND . Vice versa if the MSB index is totally different then their bitwise XOR worth can be larger than the bitwise AND worth. Think about the beneath instance to grasp this sentence.

Comply with the beneath steps to resolve this drawback:

  • Assemble an MSB array, MSB[ i ] will signify the rely of the weather whose MSB bit’s index is i.
  • Take away (MSB[ i ]*(MSB[ i ]-1))/2 from totat . Becuase the pair whose MSB is similar will not be a legitimate pair .
  • Return the legitimate rely.

Beneath is the Implementation of the above method:

C++

  

#embody <bits/stdc++.h>

utilizing namespace std;

int MSB[32];

  

lengthy lengthy valid_pairs(int arr[], int N)

{

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

        

        int MSB_index = log2(arr[i]);

        MSB[MSB_index]++;

    }

  

    lengthy lengthy tot = (N * (N - 1)) / 2;

  

    lengthy lengthy invalid = 0;

  

    

    

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

        invalid += ((MSB[i] * 1LL * (MSB[i] - 1)) / 2);

  

    lengthy lengthy legitimate = tot - invalid;

    return legitimate;

}

  

int most important()

{

    int N = 3;

    int arr[] = { 12, 4, 15 };

    cout << valid_pairs(arr, N);

}

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

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments