Given two numbers N and K, the task is to find the minimum value X such that N < X*K.
Examples:
Input: N = 8, K = 7
Output: 2
Explanation:
Numbers less than K divisible by N are 1, 2 and 4.
So the minimum value of X is 2 such that 8 < 2*7 = 14.
Input: N = 999999733, K = 999999732
Output: 999999733
Explanation:
Since 999999733 is a prime number, so 999999733 is divisible by 1 and the number itself. Since K is less than 999999733.
So the minimum value of X is 999999733 such that 999999733 < 999999733*999999732.
Naive Approach: The given problem statement can be visualized as equation K * X = N. In this equation, the objective is to minimize X. So we have to find the maximum K which divides N. Below are the steps:
- Iterate over [1, K].
- Check for each number i such that (N % i) = 0. Keep updating the max variable that stores the maximum divisor of N traversed up to i.
- The required answer is N/max.
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 value of Xvoid findMaxValue(int N, int K){ int packages; int maxi = 1; // Loop to check all the numbers // divisible by N that yield // minimum N/i value for (int i = 1; i <= K; i++) { if (N % i == 0) maxi = max(maxi, i); } packages = N / maxi; // Print the value of packages cout << packages << endl;}// Driver Codeint main(){ // Given N and K int N = 8, K = 7; // Function Call findMaxValue(N, K); return 0;} |
Java
// Java program for the above approach import java.util.Arrays;class GFG{ // Function to find the value of Xstatic void findMaxValue(int N, int K){ int packages; int maxi = 1; // Loop to check all the numbers // divisible by N that yield // minimum N/i value for(int i = 1; i <= K; i++) { if (N % i == 0) maxi = Math.max(maxi, i); } packages = N / maxi; // Print the value of packages System.out.println(packages);}// Driver code public static void main (String[] args) { // Given N and K int N = 8, K = 7; // Function call findMaxValue(N, K);} } // This code is contributed by Shubham Prakash |
Python3
# Python3 program for the above approach# Function to find the value of Xdef findMaxValue(N, K): packages = 0; maxi = 1; # Loop to check all the numbers # divisible by N that yield # minimum N/i value for i in range(1, K + 1): if (N % i == 0): maxi = max(maxi, i); packages = N // maxi; # Print value of packages print(packages);# Driver codeif __name__ == '__main__': # Given N and K N = 8; K = 7; # Function call findMaxValue(N, K);# This code is contributed by sapnasingh4991 |
C#
// C# program for the above approach using System;class GFG{ // Function to find the value of Xstatic void findMaxValue(int N, int K){ int packages; int maxi = 1; // Loop to check all the numbers // divisible by N that yield // minimum N/i value for(int i = 1; i <= K; i++) { if (N % i == 0) maxi = Math.Max(maxi, i); } packages = N / maxi; // Print the value of packages Console.WriteLine(packages);}// Driver code public static void Main(String[] args) { // Given N and K int N = 8, K = 7; // Function call findMaxValue(N, K);} } // This code is contributed by Amit Katiyar |
Javascript
<script>// Javascript program for the above approach// Function to find the value of Xfunction findMaxValue(N, K){ let packages; let maxi = 1; // Loop to check all the numbers // divisible by N that yield // minimum N/i value for (let i = 1; i <= K; i++) { if (N % i == 0) maxi = Math.max(maxi, i); } packages = parseInt(N / maxi); // Print the value of packages document.write(packages);}// Driver Code// Given N and Klet N = 8, K = 7;// Function CallfindMaxValue(N, K);// This code is contributed by rishavmahato348.</script> |
Output:
2
Time Complexity: O(K)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach we will find the factor using the efficient approach discussed in this article. Below are the steps:
- Initialize the ans variable to store the largest factor of N.
- Iterate over [1, sqrt(N)] and do the following:
- Check if N is divisible by i or not.
- If not then check for the next number.
- Else if i ? K and N/i ? K then update ans to the maximum (i, N/i).
- The value of X will be N/ans.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <iostream> using namespace std; // Function to find the largest // factor of N which is less than // or equal to K int solve(int n, int k) { // Initialise the variable to // store the largest factor of // N <= K int ans = 0; // Loop to find all factors of N for (int j = 1; j * j <= n; j++) { // Check if j is a // factor of N or not if (n % j == 0) { // Check if j <= K // If yes, then store // the larger value between // ans and j in ans if (j <= k) { ans = max(ans, j); } // Check if N/j <= K // If yes, then store // the larger value between // ans and j in ans if (n / j <= k) { ans = max(ans, n / j); } } } // Since max value is always // stored in ans, the maximum // value divisible by N less than // or equal to K will be returned. return ans; } // Driver Code int main() { // Given N and K int N = 8, K = 7; // Function Call cout << (N / solve(N, K)); return 0; } |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find the largest// factor of N which is less than// or equal to Kstatic int solve(int n, int k){ // Initialise the variable to // store the largest factor of // N <= K int ans = 0; // Loop to find all factors of N for(int j = 1; j * j <= n; j++) { // Check if j is a // factor of N or not if (n % j == 0) { // Check if j <= K // If yes, then store // the larger value between // ans and j in ans if (j <= k) { ans = Math.max(ans, j); } // Check if N/j <= K // If yes, then store // the larger value between // ans and j in ans if (n / j <= k) { ans = Math.max(ans, n / j); } } } // Since max value is always // stored in ans, the maximum // value divisible by N less than // or equal to K will be returned. return ans;}// Driver Codepublic static void main(String[] args){ // Given N and K int N = 8, K = 7; // Function call System.out.print((N / solve(N, K)));}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approach# Function to find the largest# factor of N which is less than# or equal to Kdef solve(n, k): # Initialise the variable to # store the largest factor of # N <= K ans = 0; # Loop to find all factors of N for j in range(1, n + 1): if (j * j > n): break; # Check if j is a # factor of N or not if (n % j == 0): # Check if j <= K # If yes, then store # the larger value between # ans and j in ans if (j <= k): ans = max(ans, j); # Check if N/j <= K # If yes, then store # the larger value between # ans and j in ans if (n // j <= k): ans = max(ans, n // j); # Since max value is always # stored in ans, the maximum # value divisible by N less than # or equal to K will be returned. return ans;# Driver Codeif __name__ == '__main__': # Given N and K N = 8; K = 7; # Function call print((N // solve(N, K)));# This code is contributed by gauravrajput1 |
C#
// C# program for the above approachusing System;class GFG{// Function to find the largest// factor of N which is less than// or equal to Kstatic int solve(int n, int k){ // Initialise the variable to // store the largest factor of // N <= K int ans = 0; // Loop to find all factors of N for(int j = 1; j * j <= n; j++) { // Check if j is a // factor of N or not if (n % j == 0) { // Check if j <= K // If yes, then store // the larger value between // ans and j in ans if (j <= k) { ans = Math.Max(ans, j); } // Check if N/j <= K // If yes, then store // the larger value between // ans and j in ans if (n / j <= k) { ans = Math.Max(ans, n / j); } } } // Since max value is always // stored in ans, the maximum // value divisible by N less than // or equal to K will be returned. return ans;}// Driver Codepublic static void Main(String[] args){ // Given N and K int N = 8, K = 7; // Function call Console.Write((N / solve(N, K)));}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program implementation// of the approach// Function to find the largest// factor of N which is less than// or equal to Kfunction solve(n, k){ // Initialise the variable to // store the largest factor of // N <= K let ans = 0; // Loop to find all factors of N for(let j = 1; j * j <= n; j++) { // Check if j is a // factor of N or not if (n % j == 0) { // Check if j <= K // If yes, then store // the larger value between // ans and j in ans if (j <= k) { ans = Math.max(ans, j); } // Check if N/j <= K // If yes, then store // the larger value between // ans and j in ans if (n / j <= k) { ans = Math.max(ans, n / j); } } } // Since max value is always // stored in ans, the maximum // value divisible by N less than // or equal to K will be returned. return ans;}// Driver Code // Given N and K let N = 8, K = 7; // Function call document.write((N / solve(N, K))); </script> |
Output:
2
Time Complexity: O(sqrt(N))
Auxiliary Space: 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!