Given an array arr[] of size N and a prime number P, the task is to count the elements of the array such that modulo multiplicative inverse of the element under modulo P is equal to the element itself.
Examples:
Input: arr[] = {1, 6, 4, 5}, P = 7
Output: 2
Explanation:
Modular multiplicative inverse of arr[0](=1) under modulo P(= 7) is arr[0](= 1) itself.
Modular multiplicative inverse of arr1](= 6) under modulo P(= 7) is arr[1](= 6) itself.
Therefore, the required output is 2.Input: arr[] = {1, 3, 8, 12, 12}, P = 13
Output: 3
Naive Approach: The simplest approach is to solve this problem is to traverse the array and print the count of array elements such that modulo multiplicative inverse of the element under modulo P is equal to the element itself.
Time Complexity: O(N * log P)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is based on the following observations:
If X and Y are two numbers such that (X × Y) % P = 1, then Y is modulo inverse of X.
Therefore, If Y is X itself, then (X × X) % P must be 1.
Follow the steps below to solve the problem:
- Initialize a variable, say cntElem to store the count of elements that satisfy the given condition.
- Traverse the given array and check if (arr[i] * arr[i]) % P equal to 1 or not. If found to be true then increment the count of cntElem by 1.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to get the count// of elements that satisfy// the given condition.int equvInverse(int arr[], int N, int P){ // Stores count of elements // that satisfy the condition int cntElem = 0; // Traverse the given array. for (int i = 0; i < N; i++) { // If square of current // element is equal to 1 if ((arr[i] * arr[i]) % P == 1) { cntElem++; } } return cntElem;}// Driver Codeint main(){ int arr[] = { 1, 6, 4, 5 }; int N = sizeof(arr) / sizeof(arr[0]); int P = 7; cout << equvInverse(arr, N, P);} |
Java
// Java program to implement// the above approachimport java.io.*;class GFG{// Function to get the count// of elements that satisfy// the given condition.static int equvInverse(int[] arr, int N, int P){ // Stores count of elements // that satisfy the condition int cntElem = 0; // Traverse the given array. for(int i = 0; i < N; i++) { // If square of current // element is equal to 1 if ((arr[i] * arr[i]) % P == 1) { cntElem++; } } return cntElem;}// Driver Codepublic static void main(String[] args){ int[] arr = { 1, 6, 4, 5 }; int N = arr.length; int P = 7; System.out.println(equvInverse(arr, N, P));}}// This code is contributed by akhilsaini |
Python3
# Python3 program to implement# the above approach# Function to get the count# of elements that satisfy# the given condition.def equvInverse(arr, N, P): # Stores count of elements # that satisfy the condition cntElem = 0 # Traverse the given array. for i in range(0, N): # If square of current # element is equal to 1 if ((arr[i] * arr[i]) % P == 1): cntElem = cntElem + 1 return cntElem# Driver Codeif __name__ == "__main__": arr = [ 1, 6, 4, 5 ] N = len(arr) P = 7 print(equvInverse(arr, N, P))# This code is contributed by akhilsaini |
C#
// C# program to implement// the above approachusing System;class GFG{// Function to get the count// of elements that satisfy// the given condition.static int equvInverse(int[] arr, int N, int P){ // Stores count of elements // that satisfy the condition int cntElem = 0; // Traverse the given array. for(int i = 0; i < N; i++) { // If square of current // element is equal to 1 if ((arr[i] * arr[i]) % P == 1) { cntElem++; } } return cntElem;}// Driver Codepublic static void Main(){ int[] arr = { 1, 6, 4, 5 }; int N = arr.Length; int P = 7; Console.WriteLine(equvInverse(arr, N, P));}}// This code is contributed by akhilsaini |
Javascript
<script>// Javascript program to implement// the above approach// Function to get the count// of elements that satisfy// the given condition.function equvInverse(arr, N, P){ // Stores count of elements // that satisfy the condition let cntElem = 0; // Traverse the given array. for (let i = 0; i < N; i++) { // If square of current // element is equal to 1 if ((arr[i] * arr[i]) % P == 1) { cntElem++; } } return cntElem;}// Driver Codelet arr = [ 1, 6, 4, 5 ];let N = arr.length;let P = 7;document.write(equvInverse(arr, N, P));// This code is contributed by subham348.</script> |
2
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
