Find number of pairs ( x , y ) in an array such that x ^ y > y ^ x | Python3 program to find 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 pairs is equal to number of zeroes in Y ; Find number of elements in Y [ ] with values greater than x , bisect . bisect_right 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 Code
import bisect NEW_LINE def count ( x , Y , n , NoOfY ) : NEW_LINE INDENT if x == 0 : NEW_LINE INDENT return 0 NEW_LINE DEDENT if x == 1 : NEW_LINE INDENT return NoOfY [ 0 ] NEW_LINE DEDENT idx = bisect . bisect_right ( Y , x ) NEW_LINE ans = n - idx NEW_LINE ans += NoOfY [ 0 ] + NoOfY [ 1 ] NEW_LINE if x == 2 : NEW_LINE INDENT ans -= NoOfY [ 3 ] + NoOfY [ 4 ] NEW_LINE DEDENT if x == 3 : NEW_LINE INDENT ans += NoOfY [ 2 ] NEW_LINE DEDENT return ans NEW_LINE DEDENT def count_pairs ( X , Y , m , n ) : NEW_LINE INDENT NoOfY = [ 0 ] * 5 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if Y [ i ] < 5 : NEW_LINE INDENT NoOfY [ Y [ i ] ] += 1 NEW_LINE DEDENT DEDENT Y . sort ( ) NEW_LINE total_pairs = 0 NEW_LINE for x in X : NEW_LINE INDENT total_pairs += count ( x , Y , n , NoOfY ) NEW_LINE DEDENT return total_pairs NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT X = [ 2 , 1 , 6 ] NEW_LINE Y = [ 1 , 5 ] NEW_LINE print ( " Total ▁ pairs ▁ = ▁ " , count_pairs ( X , Y , len ( X ) , len ( Y ) ) ) NEW_LINE DEDENT