# Minimum sum of two integers whose product is strictly greater than N

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 = 10Output:7Explanation:The integers are 3 and 4. Their product is 3 × 4 = 12, which is greater than N.

Input:N = 1Output:3Explanation: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.

**Time Complexity:** O(√N)**Auxiliary Space:** O(1)

**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 = 10**.^{9} - 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**.

- Find the value of middle-range
- 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 N` `void` `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 Code` `int` `main()` `{` ` ` `int` `N = 10;` ` ` `// Function Call` ` ` `minSum(N);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `import` `java.io.*;` `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)` `{` ` ` ` ` `// 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 Code` `public` `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 N` `def` `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 Code` `N ` `=` `10` `# Function Call` `minSum(N)` `# This code is contributed by Dharanendra L V` |

## C#

`// C# program for the above approach` `using` `System;` `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)` `{` ` ` ` ` `// 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 Code` `static` `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 N` `function` `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

AandB,(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 N` `void` `minSum(` `int` `N)` `{` ` ` `// Store the answer using the` ` ` `// AP-GP inequality` ` ` `int` `ans = ` `ceil` `(2 * ` `sqrt` `(N + 1));` ` ` `// Print the answer` ` ` `cout << ans;` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `N = 10;` ` ` `// Function Call` ` ` `minSum(N);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `import` `java.lang.*;` `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)` `{` ` ` ` ` `// 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 Code` `public` `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` `import` `math` `# Function to find the minimum sum of` `# two integers such that their product` `# is strictly greater than N` `def` `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 Code` `N ` `=` `10` `# Function Call` `minSum(N)` `# This code is contributed by Dharanendra L V` |

## C#

`// C# program for the above approach` `using` `System;` `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)` `{` ` ` ` ` `// 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 Code` `static` `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 N` `function` `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 Code` `let N = 10;` `// Function Call` `minSum(N);` `</script>` |

**Output:**

7

**Time Complexity:** O(1)**Auxiliary Space:** O(1)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.