XOR of array elements whose modular inverse with a given number exists | Function to return the gcd of a & b ; Base Case ; Recursively calculate GCD ; Function to print the Bitwise XOR of elements of arr [ ] if gcd ( arr [ i ] , M ) is 1 ; Initialize xor ; Traversing the array ; GCD of M and arr [ i ] ; If GCD is 1 , update xor ; Print xor ; Drive Code ; Given array arr [ ] ; Given number M ; Size of the array ; Function Call
def gcd ( a , b ) : NEW_LINE INDENT if ( a == 0 ) : NEW_LINE INDENT return b NEW_LINE DEDENT return gcd ( b % a , a ) NEW_LINE DEDENT def countInverse ( arr , N , M ) : NEW_LINE INDENT XOR = 0 NEW_LINE for i in range ( 0 , N ) : NEW_LINE INDENT gcdOfMandelement = gcd ( M , arr [ i ] ) NEW_LINE if ( gcdOfMandelement == 1 ) : NEW_LINE INDENT XOR = XOR ^ arr [ i ] NEW_LINE DEDENT DEDENT print ( XOR ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 2 , 3 ] NEW_LINE M = 4 NEW_LINE N = len ( arr ) NEW_LINE countInverse ( arr , N , M ) NEW_LINE DEDENT