Given two positive integers n and k. Find minimum positive integer x such that the (x % k) * (x / k) == n, where % is the modulus operator and / is the integer division operator.
Examples:
Input : n = 4, k = 6
Output :10
Explanation : (10 % 6) * (10 / 6) = (4) * (1) = 4 which is equal to n
Input : n = 5, k = 5
Output : 26
Approach: The problem has been solved using the value of K in the Set-1. In this article, we will use the factor method to solve the above problem. Given below are the steps to solve the above problem.
- Since the equation is of the form a*b = N, so a and b will be the factors of N.
- Iterate from 1 to sqrt(N) to get all the factors.
- The factors i and n/i can be either of A or B.
- If i is A and n/i is B then the number will be i*k + (n/i). We can check if this number is the one by comparing it with N, if it is then it is a number which satisfies the equation.
- If i is B and n/i is A then the number will be (n/i)*k + (i). We can check if this number is the one by comparing it with N, if it is then it is a number which satisfies the equation.
- Obtain all the numbers which satisfies the equation and print the smallest among them.
Below is the implementation of the above approach.
C++
// CPP Program to find the minimum // positive X such that the given // equation holds true #include <bits/stdc++.h> using namespace std; // This function gives the required // answer int minimumX( int n, int k) { int mini = INT_MAX; // Iterate for all the factors for ( int i = 1; i * i <= n; i++) { // Check if i is a factor if (n % i == 0) { int fir = i; int sec = n / i; int num1 = fir * k + sec; // Consider i to be A and n/i to be B int res = (num1 / k) * (num1 % k); if (res == n) mini = min(num1, mini); int num2 = sec * k + fir; res = (num2 / k) * (num2 % k); // Consider i to be B and n/i to be A if (res == n) mini = min(num2, mini); } } return mini; } // Driver Code to test above function int main() { int n = 4, k = 6; cout << minimumX(n, k) << endl; n = 5, k = 5; cout << minimumX(n, k) << endl; return 0; } |
Java
// Java Program to find the minimum // positive X such that the given // equation holds true import java.util.*; class solution { // This function gives the required // answer static int minimumX( int n, int k) { int mini = Integer.MAX_VALUE; // Iterate for all the factors for ( int i = 1 ; i * i <= n; i++) { // Check if i is a factor if (n % i == 0 ) { int fir = i; int sec = n / i; int num1 = fir * k + sec; // Consider i to be A and n/i to be B int res = (num1 / k) * (num1 % k); if (res == n) mini = Math.min(num1, mini); int num2 = sec * k + fir; res = (num2 / k) * (num2 % k); // Consider i to be B and n/i to be A if (res == n) mini = Math.min(num2, mini); } } return mini; } // Driver Code to test above function public static void main(String args[]) { int n = 4 , k = 6 ; System.out.println(minimumX(n, k)); n = 5 ; k = 5 ; System.out.println(minimumX(n, k)); } } |
Python3
# Python3 program to find the minimum # positive X such that the given # equation holds true import sys # This function gives the required # answer def minimumX(n, k): mini = sys.maxsize # Iterate for all the factors i = 1 while i * i < = n : # Check if i is a factor if (n % i = = 0 ) : fir = i sec = n / / i num1 = fir * k + sec # Consider i to be A and n/i to be B res = (num1 / / k) * (num1 % k) if (res = = n): mini = min (num1, mini) num2 = sec * k + fir res = (num2 / / k) * (num2 % k) # Consider i to be B and n/i to be A if (res = = n): mini = min (num2, mini) i + = 1 return mini # Driver Code if __name__ = = "__main__" : n = 4 k = 6 print (minimumX(n, k)) n = 5 k = 5 print (minimumX(n, k)) # This code is contributed by ita_c |
C#
// C# Program to find the minimum // positive X such that the given // equation holds true using System; class solution { // This function gives the required // answer static int minimumX( int n, int k) { int mini = int .MaxValue; // Iterate for all the factors for ( int i = 1; i * i <= n; i++) { // Check if i is a factor if (n % i == 0) { int fir = i; int sec = n / i; int num1 = fir * k + sec; // Consider i to be A and n/i to be B int res = (num1 / k) * (num1 % k); if (res == n) mini = Math.Min(num1, mini); int num2 = sec * k + fir; res = (num2 / k) * (num2 % k); // Consider i to be B and n/i to be A if (res == n) mini = Math.Min(num2, mini); } } return mini; } // Driver Code to test above function public static void Main() { int n = 4, k = 6; Console.WriteLine(minimumX(n, k)); n = 5; k = 5; Console.WriteLine(minimumX(n, k)); } // This code is contributed by Ryuga } |
PHP
<?php // PHP Program to find the minimum // positive X such that the given // equation holds true // Function gives the required // answer function minimumX( $n , $k ) { $mini = PHP_INT_MAX; // Iterate for all the factors for ( $i = 1; $i * $i <= $n ; $i ++) { // Check if i is a factor if ( $n % $i == 0) { $fir = $i ; $sec = (int) $n / $i ; $num1 = $fir * $k + $sec ; // Consider i to be A and n/i to be B $res = (int)( $num1 / $k ) * ( $num1 % $k ); if ( $res == $n ) $mini = min( $num1 , $mini ); $num2 = $sec * $k + $fir ; $res = (int)( $num2 / $k ) * ( $num2 % $k ); // Consider i to be B and n/i to be A if ( $res == $n ) $mini = min( $num2 , $mini ); } } return $mini ; } // Driver Code $n = 4; $k = 6; echo minimumX( $n , $k ), "\n" ; $n = 5; $k = 5; echo minimumX( $n , $k ), "\n" ; // This code is contributed // by Sach_Code ?> |
Javascript
<script> // Javascript Program to find the minimum // positive X such that the given // equation holds true // This function gives the required // answer function minimumX(n, k) { let mini = Number.MAX_VALUE; // Iterate for all the factors for (let i = 1; i * i <= n; i++) { // Check if i is a factor if (n % i == 0) { let fir = i; let sec = parseInt(n / i, 10); let num1 = fir * k + sec; // Consider i to be A and n/i to be B let res = parseInt((num1 / k), 10) * (num1 % k); if (res == n) mini = Math.min(num1, mini); let num2 = sec * k + fir; res = parseInt((num2 / k), 10) * (num2 % k); // Consider i to be B and n/i to be A if (res == n) mini = Math.min(num2, mini); } } return mini; } let n = 4, k = 6; document.write(minimumX(n, k) + "<br>" ); n = 5, k = 5; document.write(minimumX(n, k)); </script> |
10 26
Time Complexity : O(sqrt(N)), where N is the given positive integer. As we are using a loop to traverse sqrt (N) times, as the condition is i*i <= N so taking square root in both the sides we get i<= sqrt(N).
Auxiliary Space: O(1), as we are not using any extra space.