# SANDO- Editorial

Code Battle: Holi Edition

Author: Rahul Sharma

Tester: Rahul Sharma

Editorialist: Deepanshu Jindal

Easy

# PREREQUISITES:

Basic Math, Basic knowledge of programming

# PROBLEM:

Given a natural number N, break it into two non-negative integers say a and b such that:

1. Condition 1: - gcd(a, b) = min(a, b)

2. Condition 2: - Absolute difference |a−b| is minimum.

If not possible, Print -1

# QUICK EXPLANATION:

Given, a + b = N and gcd(a, b) = min(a, b), we can conclude that N % min(a, b) = 0. Moreover, to make |a-b| to be minimum, they should be as much close to \frac {N}{2} as possible.

# EXPLANATION:

Assume that we divide N into two numbers a, b such that a \leq b.

As per condition 1 and basic mathematics, n must be divisible by a (i.e. n%a =0).

Now we need to find a, b that are as much close to N/2 (to minimize the difference) and satisfy the above conditions. For this purpose, we can see all factors of N upto square root N, and check for any kind of possible solution.

# Complexities

Time Complexity: O( \sqrt{N} ) per test case.
Auxiliary Space Complexity: O(1) per test case.

# Solutions

Setter's Solution
#include<bits/stdc++.h>
using namespace std;

int maxFactor(int n)
{
for(int i = 2; i*i <= n; i++)
if(n % i == 0)
return n/i;
return 1;
}

int main()
{
int t, n;
cin >> t;
while(t--){
cin >> n;
if(n == 1)
cout << -1 << '\n';
else{
int a =  maxFactor(n);
int b = n - a;
cout << a << ' ' << b << '\n';
}
}
}

Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

int main(){
int t;
cin>>t;
for(long long int y=0;y<t;y++){
long int n;
cin>>n;
long int a,b;

if(n==1){
cout<<-1<<"\n";
continue;
}

if(n%2==0){
cout<<n/2<<' '<<n/2<<"\n";
continue;
}
long int g=sqrt(n), ch=1;
for(long int i=3;i<=g;i=i+2){
if(n%i==0){
ch=n/i;
break;
}
}
cout<<ch<<' '<<n-ch<<"\n";
}
return 0;
}