Largest number up to N whose modulus with X is equal to Y modulo X
Given three positive integers X, Y, and N, such that Y < X, the task is to find the largest number from the range [0, N] whose modulus with X is equal to Y modulo X.
Examples:
Input: X = 10, Y = 5, N = 15
Output: 15
Explanation:
The value of 15 % 10 (= 5) and 5 % 10 (= 5) are equal.
Therefore, the required output is 15.Input: X = 5, Y = 0, N = 4
Output: 0
Approach: The given problem can be solved based on the following observations:
- Since Y is less than X, then Y % X must be Y. Therefore, the idea is to find the maximum value from the range [0, N] whose modulus with X is Y.
- Assume the maximum number, say num = N, to get the remainder modulo with X as Y.
- Subtract N with the remainder of N % X to get the remainder as 0, and then add Y to it. Then, the remainder of that number with X will be Y.
- Check if the number is less than N. If found to be true, then set num = (N – N % X + Y).
- Otherwise, again subtract the number with the value of X, i.e., num = (N – N % X – (X – Y)), to get the maximum value from the interval [0, N].
- Mathematically:
- If (N – N % X + Y) ? N, then set num = (N – N % X + Y).
- Otherwise, update num = (N – N % X – (X – Y)).
Follow the steps below to solve the problem:
- Initialize a variable, say num, to store the maximum number that has the remainder Y % X from the range [0, N].
- If (N – N % X + Y) ? N, then update num = (N – N % X + Y).
- Otherwise, update num = (N – N % X – (X – Y)).
- After completing the above steps, print the value of num as the 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 print the largest // number upto N whose modulus // with X is same as Y % X long long maximumNum( long long X, long long Y, long long N) { // Stores the required number long long num = 0; // Update num as the result if (N - N % X + Y <= N) { num = N - N % X + Y; } else { num = N - N % X - (X - Y); } // Return the resultant number return num; } // Driver Code int main() { long long X = 10; long long Y = 5; long long N = 15; cout << maximumNum(X, Y, N); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; class GFG { // Function to print the largest // number upto N whose modulus // with X is same as Y % X static long maximumNum( long X, long Y, long N) { // Stores the required number long num = 0 ; // Update num as the result if (N - N % X + Y <= N) { num = N - N % X + Y; } else { num = N - N % X - (X - Y); } // Return the resultant number return num; } // Driver Code public static void main(String[] args) { long X = 10 ; long Y = 5 ; long N = 15 ; System.out.println(maximumNum(X, Y, N)); } } // This code is contributed by Kingash. |
Python3
# Python3 program for the above approach # Function to print the largest # number upto N whose modulus # with X is same as Y % X def maximumNum(X, Y, N): # Stores the required number num = 0 # Update num as the result if (N - N % X + Y < = N): num = N - N % X + Y else : num = N - N % X - (X - Y) # Return the resultant number return num # Driver Code if __name__ = = '__main__' : X = 10 Y = 5 N = 15 print (maximumNum(X, Y, N)) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approach using System; class GFG { // Function to print the largest // number upto N whose modulus // with X is same as Y % X static long maximumNum( long X, long Y, long N) { // Stores the required number long num = 0; // Update num as the result if (N - N % X + Y <= N) { num = N - N % X + Y; } else { num = N - N % X - (X - Y); } // Return the resultant number return num; } // Driver Code public static void Main( string [] args) { long X = 10; long Y = 5; long N = 15; Console.WriteLine(maximumNum(X, Y, N)); } } // This code is contributed by ukasp. |
Javascript
<script> // Javascript program for the above approach // Function to print the largest // number upto N whose modulus // with X is same as Y % X function maximumNum(X, Y, N) { // Stores the required number let num = 0; // Update num as the result if (N - N % X + Y <= N) { num = N - N % X + Y; } else { num = N - N % X - (X - Y); } // Return the resultant number return num; } // Driver code let X = 10; let Y = 5; let N = 15; document.write(maximumNum(X, Y, N)); // This code is contributed by target_2 </script> |
Output:
15
Time Complexity: O(1)
Auxiliary Space: O(1)
Contact Us