The Coding Culture
Published in

The Coding Culture

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”.

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;
}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store