RESQ - Editorial

[vamsi_kavala]

PROBLEM LINKS:

Practice
Contest

DIFFICULTY:

Simple

PREREQUISITES:

Math, Prime Factorization

PROBLEM:

The aim is to find two numbers x and y such that x * y = N and |y – x| is as small as possible.

EXPLANATION:

This looks like a simple factorization problem, doesn’t it?

ans = INF
for x = 1 to N:
	if N mod x = 0:
		y = N / x is integer
		ans = min(ans, abs(y – x))

However, the program written by the above logic will get TLE. The reason being, N can be as large as 10⁸. It is safe to assume that a loop over 10⁸ numbers will not take less than 1 second on the CodeChef judge. And considering that the test data will have up to 100 such numbers, we cannot pass the time limit with the above solution.

The important trick here is to notice that when we consider some x in the above loop that is greater than [sqrt(N)] (the largest integer that is not greater than square root of N) then y will be less than [sqrt(N)] and it means that we have considered pair (y, x) earlier in this loop. Also for this pair we have the same absolute value of difference as for current pair (x, y) and hence we can simply skip values of x that are greater than [sqrt(N)] which transforms our program to the following one

ans = INF
for x = 1 to [sqrt(N)]:
	if N mod x = 0:
		y = N / x is integer
		ans = min(ans, y – x)

This solution has complexity O(sqrt(N)) for each test and since we have T <= 100 tests in each test file it safely fits in the time limit. Note the we get rid of abs since y now is always not less than x.

Also, as x reaches closer to [sqrt(N)] on the number line, y = N / x also reaches closer to [sqrt(N)] from the other side, i.e. as x increases, y decreases. This means that the difference between x and y is decreasing as we continue through the loop. Hence, the answer will be the difference between x and N / x where x is the largest factor of N which is not greater than [sqrt(N)]. The solution can be further optimised as:

ans = INF
for x = [sqrt(N)] downto 1:
	if N mod x = 0:
		y = N / x
		ans = y – x
		break;

SETTER’S SOLUTION:

Can be found here.

APPROACH:

The problem setter used the above approach to solve the problem.

TESTER’S SOLUTION:

Can be found here.

APPROACH:

Here, the problem tester used the above approach to solve the problem.

ALTERNATE TESTER’S SOLUTION:

Can be found here.

APPROACH:

This approach uses the Sieve of Eratosthenes algorithm for finding prime numbers. Using this, we find all the primes till sqrt(N) once and store them in an array. Since the maximum value of N is 10⁸, it is enough to find the primes till sqrt(10⁸) = 10⁴.

Now, for every given N, we find all its prime factors and store them in an array. This can be done by looping over the prime numbers that we generated earlier and checking if each of it is a factor of N. We check for only those numbers which are not greater than sqrt(N). If any of those prime numbers is a factor, we calculate the degree of that factor. By degree of a factor we mean the number of times the factor divides the number. For example, 24 = 2³.3¹. Here 2 (the prime factor) has a degree of 3 and 3(the next prime factor) has a degree of 1.

Next we try to generate all the divisors of N using the above information that we gathered. Initially our divisors array will have 1 in it (1 is a divisor of every number ). We can do this by going through each prime factor x, and multiply each element in the existing divisors array by xⁱ where 0<=i<=degree[x]. For example, let N = 84.
84 can be written as 2².3¹.7¹

Divisors: 1 Prime Factor: 2 New
Divisors: 2x1 , 2²x1

Divisors: 1, 2, 4 Prime Factor: 3 New
Divisors: 1, 2, 4, 3, 6, 12

Divisors: 1, 2, 4, 3, 6, 12 Prime
Factor: 7 New Divisors: 1, 2, 4, 3, 6,
12, 7, 14, 28, 21, 42, 84

So we finally have the array of the entire divisors. Note that we do not have these divisors in the sorted order. So we will have to check for every divisor d, and check for the minimum difference of |d – N/d|.

This approach is asymptotically better than the previous approach. Let’s look at the complexity of this solution. Generating the primes using the sieve has O(sqrt(N) * log log N) complexity. And on an average, getting all the prime factors and generating the divisors of a number will take O(sqrt(N)/log(N)) time. So the overall complexity is O(sqrt(N) * log log N + T * sqrt(N) / log(N)) .

[sobhan_cp]

hi thanks for editorial
if N=10^18 what is the solution?

[garakchy]

imho, if you noticed, the question wants “almost” square cup-cakes, that means two divisors needs to be equal or “almost” equal(nearest possible numbers). voila

[sumit6b]

Why this is so?

Since the maximum value of N is 108, it is enough to find the primes till sqrt(10^8) = 10^4.

[kartik_shenoy]

I think this is how it might be. Please correct me if I am wrong.

ans = INF
for x = 1 to [sqrt(N)]:
    if N mod x = 0:
        y = N / x is integer
        ans = min(ans, y – x)

This loop is more efficient in case N is prime.

ans = INF
for x = [sqrt(N)] downto 1:
    if N mod x = 0:
        y = N / x
        ans = y – x
    break;

And this one is more efficient in case N is composite.

Thus, depending on how the test cases are developed, the more efficient loop will be different. If the test cases have a lot of prime numbers, the first loop will be more efficient. If the test cases have a lot of composite numbers, the second loop will be more efficient.

[elli0t]

Great Editorial! These type of editorials are the reason why I check every editorial even after getting AC.

[duggu_123]

All Test Cases Passed. AC

Ideone.com

refer this link it is handling Prime cases separately.

[aditya_oke]

Great Editorial
It’s best if it is accompanied with code.
This follows the method 1. Which has O(sqrt(n)) Time complexity.

#include <bits/stdc++.h>
#include<cmath>
#define ll long long
using namespace std;

int main() 
{
    int t;
    cin>>t;
    while(t>0)
    {
        ll int n;
        cin>>n;
        ll int mindiff = n;
        ll int diff;
        for(ll int i=1; i*i<=n; i++)
        {
            if(n % i == 0)
            {
                diff = (n/i) - i;
                mindiff = min(mindiff, diff);
                // cout<<diff<<endl;
            }
        }
        cout<<mindiff<<endl;
        t -= 1;
    }
	return 0;
}