Given an array arr[] of length N and a positive integer M, the task is to find the Bitwise XOR of all the array elements whose modular inverse with M exists.
Examples:
Input: arr[] = {1, 2, 3}, M = 4
Output: 2
Explanation:
Initialize the value xor with 0:
For element indexed at 0 i.e., 1, its mod inverse with 4 is 1 because (1 * 1) % 4 = 1 i.e., it exists. Therefore, xor = (xor ^ 1) = 1.
For element indexed at 1 i.e., 2, its mod inverse does not exist.
For element indexed at 2 i.e., 3, its mod inverse with 4 is 3 because (3 * 3) % 4 = 1 i.e., it exists. Therefore, xor = (xor ^ 3) = 2.
Hence, xor is 2.Input: arr[] = {3, 6, 4, 5, 8}, M = 9
Output: 9
Explanation:
Initialize the value xor with 0:
For element indexed at 0 i.e., 3, its mod inverse does not exist.
For element indexed at 1 i.e., 6, its mod inverse does not exist.
For element indexed at 2 i.e., 4, its mod inverse with 9 is 7 because (4 * 7) % 9 = 1 i.e., it exists. Therefore, xor = (xor ^ 4) = 4.
For element indexed at 3 i.e., 5, its mod inverse with 9 is 2 because (5 * 2) % 9 = 1 i.e., it exists. Therefore, xor = (xor ^ 5) = 1.
For element indexed at 4 i.e., 8, its mod inverse with 9 is 8 because (8 * 8) % 9 = 1 i.e., it exists. Therefore, xor = (xor ^ 8) = 9.
Hence, xor is 9.
Naive Approach: The simplest approach is to print the XOR of all the elements of the array for which there exists any j where (1 <= j < M) such that (arr[i] * j) % M = 1 where 0 ? i < N.
Time Complexity: O(N * M)
Auxiliary Space: O(N)
Efficient Approach: To optimize the above approach, the idea is to use the property that the modular inverse of any number X under mod M exists if and only if the GCD of M and X is 1 i.e., gcd(M, X) is 1. Follow the steps below to solve the problem:
- Initialize a variable xor with 0, to store the xor of all the elements whose modular inverse under M exists.
- Traverse the array over the range [0, N – 1].
- If gcd(M, arr[i]) is 1 then update xor as xor = (xor^arr[i]).
- After traversing, print the value xor as the required result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to return the gcd of a & bint gcd(int a, int b){ // Base Case if (a == 0) return b; // Recursively calculate GCD return gcd(b % a, a);}// Function to print the Bitwise XOR of// elements of arr[] if gcd(arr[i], M) is 1void countInverse(int arr[], int N, int M){ // Initialize xor int XOR = 0; // Traversing the array for (int i = 0; i < N; i++) { // GCD of M and arr[i] int gcdOfMandelement = gcd(M, arr[i]); // If GCD is 1, update xor if (gcdOfMandelement == 1) { XOR ^= arr[i]; } } // Print xor cout << XOR << ' ';}// Drive Codeint main(){ // Given array arr[] int arr[] = { 1, 2, 3 }; // Given number M int M = 4; // Size of the array int N = sizeof(arr) / sizeof(arr[0]); // Function Call countInverse(arr, N, M); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{// Function to return the gcd of a & bstatic int gcd(int a, int b){ // Base Case if (a == 0) return b; // Recursively calculate GCD return gcd(b % a, a);}// Function to print the Bitwise XOR of// elements of arr[] if gcd(arr[i], M) is 1static void countInverse(int[] arr, int N, int M){ // Initialize xor int XOR = 0; // Traversing the array for(int i = 0; i < N; i++) { // GCD of M and arr[i] int gcdOfMandelement = gcd(M, arr[i]); // If GCD is 1, update xor if (gcdOfMandelement == 1) { XOR ^= arr[i]; } } // Print xor System.out.println(XOR);}// Drive Codepublic static void main(String[] args){ // Given array arr[] int[] arr = { 1, 2, 3 }; // Given number M int M = 4; // Size of the array int N = arr.length; // Function Call countInverse(arr, N, M);}}// This code is contributed by akhilsaini |
Python3
# Python3 program for the above approach# Function to return the gcd of a & bdef gcd(a, b): # Base Case if (a == 0): return b # Recursively calculate GCD return gcd(b % a, a)# Function to print the Bitwise XOR of# elements of arr[] if gcd(arr[i], M) is 1def countInverse(arr, N, M): # Initialize xor XOR = 0 # Traversing the array for i in range(0, N): # GCD of M and arr[i] gcdOfMandelement = gcd(M, arr[i]) # If GCD is 1, update xor if (gcdOfMandelement == 1): XOR = XOR ^ arr[i] # Print xor print(XOR)# Drive Codeif __name__ == '__main__': # Given array arr[] arr = [ 1, 2, 3 ] # Given number M M = 4 # Size of the array N = len(arr) # Function Call countInverse(arr, N, M)# This code is contributed by akhilsaini |
C#
// C# program for the above approachusing System;class GFG{// Function to return the gcd of a & bstatic int gcd(int a, int b){ // Base Case if (a == 0) return b; // Recursively calculate GCD return gcd(b % a, a);}// Function to print the Bitwise XOR of// elements of arr[] if gcd(arr[i], M) is 1static void countInverse(int[] arr, int N, int M){ // Initialize xor int XOR = 0; // Traversing the array for(int i = 0; i < N; i++) { // GCD of M and arr[i] int gcdOfMandelement = gcd(M, arr[i]); // If GCD is 1, update xor if (gcdOfMandelement == 1) { XOR ^= arr[i]; } } // Print xor Console.WriteLine(XOR);}// Drive Codepublic static void Main(){ // Given array arr[] int[] arr = { 1, 2, 3 }; // Given number M int M = 4; // Size of the array int N = arr.Length; // Function Call countInverse(arr, N, M);}}// This code is contributed by akhilsaini |
Javascript
<script>// Javascript program for the above approach// Function to return the gcd of a & bfunction gcd(a, b){ // Base Case if (a == 0) return b; // Recursively calculate GCD return gcd(b % a, a);}// Function to print the Bitwise XOR of// elements of arr[] if gcd(arr[i], M) is 1function countInverse(arr, N, M){ // Initialize xor var XOR = 0; // Traversing the array for(var i = 0; i < N; i++) { // GCD of M and arr[i] var gcdOfMandelement = gcd(M, arr[i]); // If GCD is 1, update xor if (gcdOfMandelement == 1) { XOR ^= arr[i]; } } // Print xor document.write(XOR);}// Driver Code// Given array arr[]var arr = [ 1, 2, 3 ];// Given number Mvar M = 4;// Size of the arrayvar N = arr.length;// Function CallcountInverse(arr, N, M);// This code is contributed by Kirti</script> |
2
Time Complexity: O(N*log M)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
