Solving MINI2: Find Minimum

In this blog, we will look at how you could approach the problem “Find Minimum” in The Coding Culture’s November Contest “Get Set and Code”.

Contest Page | CodeChef

The problem statement goes like so:

Yash likes playing with numbers. He has a challenge for you. Yash gives you a number that he made by multiplying two numbers. He claims that the possible sum of the two numbers he multiplied is as minimum as possible. He challenges you to find that minimum sum.
Formally, for a given value of N, you are required to find the minimum sum of two distinct numbers x and y such that x, y > 0 and xy = N.

The Idea

We know, (x + y)² = (x − y)² + 4xy= (x − y)² + 4N
So in order to minimize x + y, we have to minimize |x − y|. Hence out of all factors that form N on multiplication, we need to choose those factors that are
closest to each other, but is not equal to each other. One could this very easily in O(√n) time as shown below.

Solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve() {
    ll n; cin >> n;
    ll ans = LLONG_MAX;
    for (ll i = 1; i <= sqrt(n); i++) if (n % i == 0 && n/i != i) 
        ans = min(ans, i + n/i);
    cout << ans << endl;
}
int main() {
    ll t; cin >> t;
    while (t--) solve();
    return 0;
}