Given three integers N, X, and Y, the task is to find out the largest positive integer K such that K % X = Y where 0 ≤ K ≤ N. Print -1 if no such K exists.
Examples:
Input: N = 15, X = 10, Y = 5
Output:15
Explanation:
As 15 % 10 = 5Input: N = 187, X = 10, Y = 5
Output: 185
Naive Approach: The simplest approach to solve the problem is to check for each possible value of K in the range [0, N], whether the condition K % X = Y is satisfied or not. If no such K exists, print -1. Otherwise, print the largest possible value of K from the range that satisfied the condition.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the largest// positive integer K such that K % x = yint findMaxSoln(int n, int x, int y){ // Stores the minimum solution int ans = INT_MIN; for (int k = 0; k <= n; k++) { if (k % x == y) { ans = max(ans, k); } } // Return the maximum possible value return ((ans >= 0 && ans <= n) ? ans : -1);}// Driver Codeint main(){ int n = 15, x = 10, y = 5; cout << findMaxSoln(n, x, y); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find the largest// positive integer K such that K % x = ystatic int findMaxSoln(int n, int x, int y){ // Stores the minimum solution int ans = Integer.MIN_VALUE; for(int k = 0; k <= n; k++) { if (k % x == y) { ans = Math.max(ans, k); } } // Return the maximum possible value return ((ans >= 0 && ans <= n) ? ans : -1);}// Driver Codepublic static void main(String[] args){ int n = 15, x = 10, y = 5; System.out.print(findMaxSoln(n, x, y));}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program for the above approachimport sys # Function to find the largest# positive integer K such that# K % x = ydef findMaxSoln(n, x, y): # Stores the minimum solution ans = -sys.maxsize for k in range(n + 1): if (k % x == y): ans = max(ans, k) # Return the maximum possible value return (ans if (ans >= 0 and ans <= n) else -1) # Driver Codeif __name__ == '__main__': n = 15 x = 10 y = 5 print(findMaxSoln(n, x, y)) # This code is contributed by Amit Katiyar |
C#
// C# program for the above approachusing System;class GFG{// Function to find the largest// positive integer K such that // K % x = ystatic int findMaxSoln(int n, int x, int y){ // Stores the minimum solution int ans = int.MinValue; for(int k = 0; k <= n; k++) { if (k % x == y) { ans = Math.Max(ans, k); } } // Return the maximum possible value return ((ans >= 0 && ans <= n) ? ans : -1);} // Driver Codepublic static void Main(String[] args){ int n = 15, x = 10, y = 5; Console.Write(findMaxSoln(n, x, y));}}// This code is contributed by shikhasingrajput |
Javascript
<script>// Javascript program for the above approach// Function to find the largest// positive integer K such that K % x = yfunction findMaxSoln(n, x, y){ // Stores the minimum solution var ans = -1000000000; for (var k = 0; k <= n; k++) { if (k % x == y) { ans = Math.max(ans, k); } } // Return the maximum possible value return ((ans >= 0 && ans <= n) ? ans : -1);}// Driver Codevar n = 15, x = 10, y = 5;document.write( findMaxSoln(n, x, y));// This code is contributed by rrrtnx.</script> |
Output
15
Time Complexity: O(N)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the observation that K can obtain one of the following values to satisfy the equation:
K = N – N % X + Y
or
K = N – N % X + Y – X
Follow the steps below to solve the problem:
- Calculate K1 as K = N – N % X + Y and K2 as K = N – N%X + Y – X.
- If K1 lies in the range [0, N], print K1.
- Otherwise, if K2 lies in the range [0, N], print K2.
- Otherwise, print -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 find the largest positive// integer K such that K % x = yint findMaxSoln(int n, int x, int y){ // Possible value of K as K1 if (n - n % x + y <= n) { return n - n % x + y; } // Possible value of K as K2 else { return n - n % x - (x - y); }}// Driver Codeint main(){ int n = 15, x = 10, y = 5; int ans = findMaxSoln(n, x, y); cout << ((ans >= 0 && ans <= n) ? ans : -1);} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{// Function to find the largest positive// integer K such that K % x = ystatic int findMaxSoln(int n, int x, int y){ // Possible value of K as K1 if (n - n % x + y <= n) { return n - n % x + y; } // Possible value of K as K2 else { return n - n % x - (x - y); }}// Driver Codepublic static void main(String[] args){ int n = 15, x = 10, y = 5; int ans = findMaxSoln(n, x, y); System.out.print(((ans >= 0 && ans <= n) ? ans : -1));}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program to implement# the above approach# Function to find the largest positive# integer K such that K % x = ydef findMaxSoln(n, x, y): # Possible value of K as K1 if (n - n % x + y <= n): return n - n % x + y; # Possible value of K as K2 else: return n - n % x - (x - y);# Driver Codeif __name__ == '__main__': n = 15; x = 10; y = 5; ans = findMaxSoln(n, x, y); print(( ans if (ans >= 0 and ans <= n) else -1));# This code is contributed by 29AjayKumar |
C#
// C# program to implement// the above approachusing System;class GFG{// Function to find the largest // positive integer K such that // K % x = ystatic int findMaxSoln(int n, int x, int y){ // Possible value of K as K1 if (n - n % x + y <= n) { return n - n % x + y; } // Possible value of K as K2 else { return n - n % x - (x - y); }}// Driver Codepublic static void Main(String[] args){ int n = 15, x = 10, y = 5; int ans = findMaxSoln(n, x, y); Console.Write(((ans >= 0 && ans <= n) ? ans : -1));}}// This code is contributed by shikhasingrajput |
Javascript
<script>// Javascript program to implement// the above approach // Function to find the largest positive // integer K such that K % x = y function findMaxSoln(n , x , y) { // Possible value of K as K1 if (n - n % x + y <= n) { return n - n % x + y; } // Possible value of K as K2 else { return n - n % x - (x - y); } } // Driver Code var n = 15, x = 10, y = 5; var ans = findMaxSoln(n, x, y); document.write( ((ans >= 0 && ans <= n) ? ans : -1) );// This code contributed by umadevi9616</script> |
Output
15
Time Complexity: O(1)
Auxiliary Space: O(1)
Brute Force in python:
Approach:
We can simply iterate from N to 0 and check if each number K modulo X is equal to Y. The first number we find will be the largest possible value of K.
- Define a function called largest_possible_value_of_K that takes in three integer inputs: N, X, and Y.
- Use a for loop to iterate from N down to 0. Each iteration represents a possible value of K.
- Check if K modulo X is equal to Y. If it is, return K as the largest possible value of K.
- If the for loop completes without finding a suitable value of K, return -1 to indicate that no solution was found.
C++
#include <iostream>int largest_possible_value_of_K(int N, int X, int Y) { for (int K = N; K >= 0; K--) { if (K % X == Y) { return K; } } return -1;}int main() { int N = 15; int X = 10; int Y = 5; std::cout << largest_possible_value_of_K(N, X, Y) << std::endl; // Output: 15 N = 187; X = 10; Y = 5; std::cout << largest_possible_value_of_K(N, X, Y) << std::endl; // Output: 185 return 0;} |
Java
import java.util.Scanner;public class Main { // Function to find the largest possible value of K static int largestPossibleValueOfK(int N, int X, int Y) { for (int K = N; K >= 0; K--) { if (K % X == Y) { return K; } } return -1; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int N = 15; int X = 10; int Y = 5; System.out.println( largestPossibleValueOfK(N, X, Y)); // Output: 15 N = 187; X = 10; Y = 5; System.out.println(largestPossibleValueOfK( N, X, Y)); // Output: 185 scanner.close(); }} |
Python3
def largest_possible_value_of_K(N, X, Y): for K in range(N, -1, -1): if K % X == Y: return K return -1# Example usageN = 15X = 10Y = 5print(largest_possible_value_of_K(N, X, Y)) # Output: 15N = 187X = 10Y = 5print(largest_possible_value_of_K(N, X, Y)) # Output: 185 |
C#
using System;class GFG{ // Function to find the largest possible value of K static int LargestPossibleValueOfK(int N, int X, int Y) { for (int K = N; K >= 0; K--) { if (K % X == Y) { return K; } } return -1; } static void Main() { int N = 15; int X = 10; int Y = 5; Console.WriteLine(LargestPossibleValueOfK(N, X, Y)); // Output: 15 N = 187; X = 10; Y = 5; Console.WriteLine(LargestPossibleValueOfK(N, X, Y)); // Output: 185 }} |
Javascript
function GFG(N, X, Y) { // Start from N and decrement K until a valid K is found for (let K = N; K >= 0; K--) { if (K % X === Y) { return K; } } // If no valid K is found // return -1 return -1;}// Main functionfunction main() { let N = 15; let X = 10; let Y = 5; console.log(GFG(N, X, Y)); // Output: 15 N = 187; X = 10; Y = 5; console.log(GFG(N, X, Y)); // Output: 185}// Call the main functionmain(); |
Output
15 185
Time Complexity: O(N)
Space Complexity: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
