SANDO- Editorial

editorial
,
1

PROBLEM LINK:

Code Battle: Holi Edition

Author: Rahul Sharma

Tester: Rahul Sharma

Editorialist: Deepanshu Jindal

DIFFICULTY:

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