Problem : The One Who Knocks!
Setter: Aman Singhal
Tester: Yashodhan Agnihotri
Editorialist: Aman Singhal
DIFFICULTY:
Cakewalk
PREREQUISITES:
Basic Programming, Ad-hoc
PROBLEM:
You are given two values X and Y. You have to choose one positive odd integer ‘a’ and one positive even integer ‘b’. In one operation you can either add a to X or subtract b from X. You cannot change a and b once you start performing operations. You have to find the minimum number of operations to obtain Y from X.
QUICK EXPLANATION:
- When X>Y, it will take 1 operation if the difference is even, else 2.
- When X<Y, it will take 1 operation when difference is odd, 2 when difference is even but not divisible by 4 else 3.
- When X=Y, it will take 0 operation.
EXPLANATION:
There are 3 cases to be solved in this question:
Case 1: When X>Y
Tap to view
- In this case we have to decrease the value of X. We can only subtract the even value. So, if the difference is even then in one round we can reach Y .
X-b=Y - Now for odd differences, the observation here is that the difference of an even and odd number is always odd. So we can add any odd number and now subtract the difference as it will be an even number.
X+a-b=Y
Case 2: When X<Y
Tap to view
-
In this case we have to increase the value of X. We can add the odd value. So, if our difference is odd then in one round we can reach Y.
X+a= Y -
When our difference is even then we have to perform at least two operations. We can add the odd number twice as the sum of two odd numbers will give an even number but this even number will not be divisible by 4. In such cases where our difference is even and not divisible by 4 it will take 2 operations.
X+a+a = Y -
Now our last case, when we have difference as even and divisible by 4, we can achieve Y by adding two odd numbers giving sum greater than difference and then subtract the even number in order to achieve Y. In this case it will take 3 operations.
X+a+a-b = Y
Case 3: When X=Y
Tap to view
- In this case we don’t need to perform any operation.
X=Y
TIME COMPLEXITY:
- Time complexity per test case is O(1).
SOLUTIONS
Setter’s Solution (Python 3)
T=int(input())
for _ in range(T):
X,Y=map(int,input().split())
diff=abs(X-Y)
if(X>Y):
if (diff%2==0):
ans=1
else:
ans=2
elif (X<Y):
if (diff%2!=0):
ans=1
elif (diff%4==0):
ans=3
else:
ans=2
else:
ans=0
print(ans)
Tester’s Solution (C++)
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define zapp ios::sync_with_stdio(false);cin.tie(0)
int main()
{
zapp;
ll t;
cin >> t;
while (t--)
{
ll x, y;
cin >> x >> y;
ll moves = 0;
if (x > y) {
ll diff = x - y;
if (diff % 2 == 0)
moves = 1;
else
moves = 2;
}
else if (x < y) {
ll diff = y - x;
if (diff % 2)
moves = 1;
else if (diff % 2 == 0 && (diff / 2) % 2)
moves = 2;
else
moves = 3;
}
cout << moves << "\n";
}
return 0;
}
Feel free to share your approach. In case of any doubt or anything is unclear please ask it in the comment section. Any suggestions are welcomed.