Given a prime number N, the task is to find the closest smaller number than N such that modulo multiplicative inverse of a number under modulo N is equal to the number itself.
Examples:
Input: N = 7
Output: 6
Explanation:
Modulo multiplicative inverse of all possible natural numbers from 1 to less than N are:
Modulo multiplicative inverse of 1 under modulo N(=7) is 1.
Modulo multiplicative inverse of 2 under modulo N(=7) is 4.
Modulo multiplicative inverse of 3 under modulo N(=7) is 5.
Modulo multiplicative inverse of 4 under modulo N(=7) is 2.
Modulo multiplicative inverse of 5 under modulo N(=7) is 3.
Modulo multiplicative inverse of 6 under modulo N(=7) is 6.
Therefore, the nearest smaller number to N(= 7) having modulo inverse equal to the number itself is 6.Input: N = 11
Output: 10
Naive Approach: The simplest approach to solve this problem is to traverse all natural numbers from 1 to N and find the largest number such that modulo multiplicative inverse of the number under modulo N is equal to the number itself.
Time Complexity: O(N * log N)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach the idea is based on the following observations:
The nearest smaller number to N having modulo multiplicative inverse equal to the number itself is (N – 1).
Mathematical proof:
If X and Y are two numbers such that (X * Y) % N = 1 mod(N), then Y is modulo inverse of X.
Put X = N – 1 then
=>((N – 1) * Y) % N = 1 mod(N)
=>(N × Y) % N – Y % N = 1 mod(N)
=> Y = N – 1
Therefore, for X = N – 1 the value of Y is equal to X.
Therefore, to solve the problem, simply print N – 1 as the required answer.
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 find the nearest// smaller number satisfying// the conditionint clstNum(int N){ return (N - 1);}// Driver Codeint main(){ int N = 11; cout << clstNum(N);} |
Java
// Java program to implement// the above approachimport java.io.*;class GFG{// Function to find the nearest// smaller number satisfying// the conditionstatic int clstNum(int N){ return (N - 1); }// Driver Codepublic static void main(String[] args){ int N = 11; System.out.println(clstNum(N));}}// This code is contributed by akhilsaini |
Python3
# Python3 program to implement# the above approach# Function to find the nearest# smaller number satisfying# the conditiondef clstNum(N): return (N - 1)# Driver Codeif __name__ == '__main__': N = 11 print(clstNum(N)) # This code is contributed by akhilsaini |
C#
// C# program to implement// the above approachusing System;class GFG{// Function to find the nearest// smaller number satisfying// the conditionstatic int clstNum(int N){ return (N - 1); }// Driver Codepublic static void Main(){ int N = 11; Console.Write(clstNum(N));}}// This code is contributed by akhilsaini |
Javascript
<script>// Javascript program to implement// the above approach// Function to find the nearest// smaller number satisfying// the conditionfunction clstNum(N){ return (N - 1);}// Driver Codelet N = 11;document.write(clstNum(N));// This code is contributed by subham348.</script> |
10
Time Complexity: O(1)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
