Find number of pairs ( x , y ) in an array such that x ^ y > y ^ x | C ++ program to finds the number of pairs ( x , y ) in an array such that x ^ y > y ^ x ; Function to return count of pairs with x as one element of the pair . It mainly looks for all values in Y [ ] where x ^ Y [ i ] > Y [ i ] ^ x ; If x is 0 , then there cannot be any value in Y such that x ^ Y [ i ] > Y [ i ] ^ x ; If x is 1 , then the number of pais is equal to number of zeroes in Y [ ] ; Find number of elements in Y [ ] with values greater than x upper_bound ( ) gets address of first greater element in Y [ 0. . n - 1 ] ; If we have reached here , then x must be greater than 1 , increase number of pairs for y = 0 and y = 1 ; Decrease number of pairs for x = 2 and ( y = 4 or y = 3 ) ; Increase number of pairs for x = 3 and y = 2 ; Function to return count of pairs ( x , y ) such that x belongs to X [ ] , y belongs to Y [ ] and x ^ y > y ^ x ; To store counts of 0 , 1 , 2 , 3 and 4 in array Y ; Sort Y [ ] so that we can do binary search in it ; Initialize result ; Take every element of X and count pairs with it ; Driver program
#include <bits/stdc++.h> NEW_LINE using namespace std ; int count ( int x , int Y [ ] , int n , int NoOfY [ ] ) { if ( x == 0 ) return 0 ; if ( x == 1 ) return NoOfY [ 0 ] ; int * idx = upper_bound ( Y , Y + n , x ) ; int ans = ( Y + n ) - idx ; ans += ( NoOfY [ 0 ] + NoOfY [ 1 ] ) ; if ( x == 2 ) ans -= ( NoOfY [ 3 ] + NoOfY [ 4 ] ) ; if ( x == 3 ) ans += NoOfY [ 2 ] ; return ans ; } int countPairs ( int X [ ] , int Y [ ] , int m , int n ) { int NoOfY [ 5 ] = { 0 } ; for ( int i = 0 ; i < n ; i ++ ) if ( Y [ i ] < 5 ) NoOfY [ Y [ i ] ] ++ ; sort ( Y , Y + n ) ; int total_pairs = 0 ; for ( int i = 0 ; i < m ; i ++ ) total_pairs += count ( X [ i ] , Y , n , NoOfY ) ; return total_pairs ; } int main ( ) { int X [ ] = { 2 , 1 , 6 } ; int Y [ ] = { 1 , 5 } ; int m = sizeof ( X ) / sizeof ( X [ 0 ] ) ; int n = sizeof ( Y ) / sizeof ( Y [ 0 ] ) ; cout << " Total ▁ pairs ▁ = ▁ " << countPairs ( X , Y , m , n ) ; return 0 ; }