PROBLEM LINK:
Author and Editorialist: Pankaj Sharma
Tester: Jatin Kashyap
DIFFICULTY:
CAKEWALK.
PREREQUISITES:
Basics of Maths.
PROBLEM:
You are given an integer N.
Your task is to find any two integers A,B such that 1\leq A , B \leq 2*N and difference of A and B exactly equals to N i.e. A - B = N.
QUICK EXPLANATION:
Check
Answer is A = N + 1 and B = 1
EXPLANATION:
Let’s try to brute force i.e. generate all pairs of (A, B) such that between 1 \leq A, B, \leq 2*N and run two loops to check whether A - B == N or not.
Code
#include<iostream>
using namespace std;
int main()
{
int t;
// Input number of test cases
cin >> t;
while (t--) {
int N;
// Input N
cin >> N;
for (int A = 1; A <= 2 * N; A++)
{
bool foundAnswer = false;
for (int B = 1; B <= 2 * N; B++)
{
if (A - B == N) {
cout << A << " " << B << "\n";
foundAnswer = true;
break;
}
}
if (foundAnswer == true) {
break;
}
}
}
return 0;
}
Above code will result in TLE i.e. Time Limit Exceeded error as N can be 10^9 and T can be 10^5 and 1 second = 10^8 operations but we are performing around 10^{14} operations as N * T = 10^9 * 10^5 = 10^{14}
So we need to think about something different.
We if closely observe
A - B = N can be written as A = N + B
Now A \leq 2*N
So , N + B \leq 2 * N
So, B \leq N
Hence B lies between [1, N] and A lies between [N + 1, 2 * N].
Minimum value of N can be 1.
So B = 1 and A = N + 1 will be a valid answer.
Also A = 2*N and B = N is also a valid answer.
But A = 2 and B = N + 2 fails on case when N = 1 as B becomes greater than 2 * N
Time Complexity:
The time complexity is O(1) per test case.
SOLUTIONS:
Setter's Solution
#include<iostream>
using namespace std;
int main()
{
int t;
// Input number of test cases
cin >> t;
while (t--) {
int N;
// Input N
cin >> N;
int A = N + 1, B = 1;
// Print A,B in newline
cout << A << " " << B << "\n";
}
return 0;
}
Tester's Solution
import java.util.*;
class test{
public static void main (String args[]){
Scanner sc=new Scanner(System.in);
for(int i=sc.nextInt();i>0;i--)
System.out.println((sc.nextInt()+1)+" 1");
}
}
Editorialist's Solution
#include<iostream>
using namespace std;
int main()
{
int t;
// Input number of test cases
cin >> t;
while (t--) {
int N;
// Input N
cin >> N;
int A = N + 1, B = 1;
// Print A,B in newline
cout << A << " " << B << "\n";
}
return 0;
}
For doubts, please leave them in the comment section, I’ll address them.