Given an integer N, the task is to find two integers with minimum possible sum such that their product is strictly greater than N.
Examples:
Input: N = 10
Output: 7
Explanation: The integers are 3 and 4. Their product is 3 × 4 = 12, which is greater than N.Input: N = 1
Output: 3
Explanation: The integers are 1 and 2. Their product is 1 × 2 = 2, which is greater than N.
Naive Approach: Let the required numbers be A and B. The idea is based on the observation that in order to minimize their sum A should be the smallest number greater than √N. Once A is found, B will be equal to the smallest number for which A×B > N, which can be found linearly.
Steps to implement-
- Declare two variables first and second to store the answer
- Find the square root of the given number
- The first number will be that integer which is just greater than the square root
- Find the second number by running a loop
- In the last print the sum of the first and the second number
Code-
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum sum of// two integers such that their product// is strictly greater than Nvoid minSum(int N){ //To store first and second number int first,second; //Finding square root of given number float root=sqrt(N); int sq_root=(int)root; //First number will be that integer which //is just greater than square root of N first=sq_root+1; //Finding second number for(int i=1;i<=N;i++){ if((first*i)>N){ second=i; break; } } //Printing their sum cout<<first+second<<endl;}// Driver Codeint main(){ int N = 10; // Function Call minSum(N); return 0;} |
Java
// Java program for the above approachimport java.util.*;public class GFG { // Function to find the minimum sum of // two integers such that their product // is strictly greater than N static void minSum(int N) { // To store first and second number int first, second = 0; // Finding square root of given number double root = Math.sqrt(N); int sq_root = (int)Math.ceil(root); // First number will be that integer which // is just greater than or equal to the square root // of N first = sq_root; // Finding second number for (int i = 1; i <= N; i++) { if ((first * i) > N) { second = i; break; } } // Printing their sum System.out.println(first + second); } // Driver Code public static void main(String[] args) { int N = 10; // Function Call minSum(N); }} |
Javascript
//JavaScript program for the above approach// Function to find the minimum sum of// two integers such that their product// is strictly greater than Nfunction minSum(N){ //To store first and second number let first,second; //Finding square root of given number let root=Math.sqrt(N); let sq_root=Math.floor(root); //First number will be that integer which //is just greater than square root of N first=sq_root+1; //Finding second number for(let i=1;i<=N;i++){ if((first*i)>N){ second=i; break; } } //Printing their sum console.log(first+second);}// Driver Code let N = 10; // Function Call minSum(N); |
Output-
7
Time Complexity: O(N)+O(logN)=O(N),O(N) in loop and O(logN) in finding square root
Auxiliary Space: O(1), because no extra space has been used
Efficient Approach: The above solution can be optimized by using Binary Search to find A and B. Follow the steps below to solve the problem:
- Initialize two variables low = 0 and high = 109.
- Iterate until (high – low) is greater than 1 and do the following:
- Find the value of middle-range mid as (low + high)/2.
- Now, compare √N with the middle element mid, and if √N is less than or equal to the middle element, then high as mid.
- Else, update low as mid.
- After all the above steps set A = high.
- Repeat the same procedure to find B such that A×B > N.
- After the above steps, print the sum of A and B as the result.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;#define ll long long int// Function to find the minimum sum of// two integers such that their product// is strictly greater than Nvoid minSum(int N){ // Initialise low as 0 and // high as 1e9 ll low = 0, high = 1e9; // Iterate to find the first number while (low + 1 < high) { // Find the middle value ll mid = low + (high - low) / 2; // If mid^2 is greater than // equal to A, then update // high to mid if (mid * mid >= N) { high = mid; } // Otherwise update low else { low = mid; } } // Store the first number ll first = high; // Again, set low as 0 and // high as 1e9 low = 0; high = 1e9; // Iterate to find the second number while (low + 1 < high) { // Find the middle value ll mid = low + (high - low) / 2; // If first number * mid is // greater than N then update // high to mid if (first * mid > N) { high = mid; } // Else, update low to mid else { low = mid; } } // Store the second number ll second = high; // Print the result cout << first + second;}// Driver Codeint main(){ int N = 10; // Function Call minSum(N); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG{ // Function to find the minimum sum of// two integers such that their product// is strictly greater than Nstatic void minSum(int N){ // Initialise low as 0 and // high as 1e9 long low = 0, high = 1000000000; // Iterate to find the first number while (low + 1 < high) { // Find the middle value long mid = low + (high - low) / 2; // If mid^2 is greater than // equal to A, then update // high to mid if (mid * mid >= N) { high = mid; } // Otherwise update low else { low = mid; } } // Store the first number long first = high; // Again, set low as 0 and // high as 1e9 low = 0; high = 1000000000; // Iterate to find the second number while (low + 1 < high) { // Find the middle value long mid = low + (high - low) / 2; // If first number * mid is // greater than N then update // high to mid if (first * mid > N) { high = mid; } // Else, update low to mid else { low = mid; } } // Store the second number long second = high; // Print the result System.out.println(first + second);}// Driver Codepublic static void main(String[] args){ int N = 10; // Function Call minSum(N);}}// This code is contributed by Dharanendra L V |
Python3
# Python3 program for the above approach# Function to find the minimum sum of# two integers such that their product# is strictly greater than Ndef minSum(N): # Initialise low as 0 and # high as 1e9 low = 0 high = 1000000000 # Iterate to find the first number while (low + 1 < high): # Find the middle value mid = low + (high - low) / 2 # If mid^2 is greater than # equal to A, then update # high to mid if (mid * mid >= N): high = mid # Otherwise update low else: low = mid # Store the first number first = high # Again, set low as 0 and # high as 1e9 low = 0 high = 1000000000 # Iterate to find the second number while (low + 1 < high): # Find the middle value mid = low + (high - low) / 2 # If first number * mid is # greater than N then update # high to mid if (first * mid > N): high = mid # Else, update low to mid else: low = mid # Store the second number second = high # Print the result print(round(first + second))# Driver CodeN = 10# Function CallminSum(N)# This code is contributed by Dharanendra L V |
C#
// C# program for the above approachusing System;class GFG{ // Function to find the minimum sum of// two integers such that their product// is strictly greater than Nstatic void minSum(int N){ // Initialise low as 0 and // high as 1e9 long low = 0, high = 1000000000; // Iterate to find the first number while (low + 1 < high) { // Find the middle value long mid = low + (high - low) / 2; // If mid^2 is greater than // equal to A, then update // high to mid if (mid * mid >= N) { high = mid; } // Otherwise update low else { low = mid; } } // Store the first number long first = high; // Again, set low as 0 and // high as 1e9 low = 0; high = 1000000000; // Iterate to find the second number while (low + 1 < high) { // Find the middle value long mid = low + (high - low) / 2; // If first number * mid is // greater than N then update // high to mid if (first * mid > N) { high = mid; } // Else, update low to mid else { low = mid; } } // Store the second number long second = high; // Print the result Console.WriteLine( first + second);}// Driver Codestatic public void Main(){ int N = 10; // Function Call minSum(N);}}// This code is contributed by Dharanendra L V |
Javascript
<script>// Javascript program for the above approach// Function to find the minimum sum of// two integers such that their product// is strictly greater than Nfunction minSum(N){ // Initialise low as 0 and // high as 1e9 let low = 0, high = 1000000000; // Iterate to find the first number while (low + 1 < high) { // Find the middle value let mid = low + parseInt((high - low) / 2); // If mid^2 is greater than // equal to A, then update // high to mid if (mid * mid >= N) { high = mid; } // Otherwise update low else { low = mid; } } // Store the first number let first = high; // Again, set low as 0 and // high as 1e9 low = 0; high = 1000000000; // Iterate to find the second number while (low + 1 < high) { // Find the middle value let mid = low + parseInt((high - low) / 2); // If first number * mid is // greater than N then update // high to mid if (first * mid > N) { high = mid; } // Else, update low to mid else { low = mid; } } // Store the second number let second = high; // Print the result document.write(first + second);}// Driver Code let N = 10; // Function Call minSum(N);// This code is contributed by rishavmahato348.</script> |
Output
7
Time Complexity: O(log N)
Auxiliary Space: O(1)
Most Efficient Approach: To optimize the above approach, the idea is based on Inequality of Arithmetic and Geometric progression as illustrated below.
From the inequality, If there are two integers A and B,
(A + B)/2 ≥ √(A×B)
Now, A×B = Product of the two integers, which is N and A+B is sum(=S).
Therefore, S ≥ 2*√N
To get strictly greater product than N, the above equation transforms to: S ≥ 2*√(N+1)
Below is the program for the above approach:
C++14
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum sum of// two integers such that their product// is strictly greater than Nvoid minSum(int N){ // Store the answer using the // AP-GP inequality int ans = ceil(2 * sqrt(N + 1)); // Print the answer cout << ans;}// Driver Codeint main(){ int N = 10; // Function Call minSum(N); return 0;} |
Java
// Java program for the above approachimport java.lang.*;class GFG{ // Function to find the minimum sum of// two integers such that their product// is strictly greater than Nstatic void minSum(int N){ // Store the answer using the // AP-GP inequality int ans = (int)Math.ceil(2 * Math.sqrt(N + 1)); // Print the answer System.out.println( ans);}// Driver Codepublic static void main(String[] args){ int N = 10; // Function Call minSum(N);}}// This code is contributed by Dharanendra L V |
Python3
# Python3 program for the above approachimport math# Function to find the minimum sum of# two integers such that their product# is strictly greater than Ndef minSum(N): # Store the answer using the # AP-GP inequality ans = math.ceil(2 * math.sqrt(N + 1)) # Print the result print(math.trunc(ans))# Driver CodeN = 10# Function CallminSum(N)# This code is contributed by Dharanendra L V |
C#
// C# program for the above approachusing System;class GFG{// Function to find the minimum sum of// two integers such that their product// is strictly greater than Nstatic void minSum(int N){ // Store the answer using the // AP-GP inequality int ans = (int)Math.Ceiling(2 * Math.Sqrt(N + 1)); // Print the answer Console.WriteLine( ans);}// Driver Codestatic public void Main(){ int N = 10; // Function Call minSum(N);}}// This code is contributed by Dharanendra L V |
Javascript
<script>// Javascript program for the above approach// Function to find the minimum sum of// two integers such that their product// is strictly greater than Nfunction minSum(N){ // Store the answer using the // AP-GP inequality let ans = Math.ceil(2 * Math.sqrt(N + 1)); // Print the answer document.write(ans);}// Driver Codelet N = 10;// Function CallminSum(N);</script> |
Output
7
Time Complexity: O(logN) because it is using inbuilt sqrt function
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!
