Page Contents
Reduce to zero Solution Codechef
Chef has two integers X and Y. Chef wants to perform some operations to make both X and Y zero simultaneously. In one operation, Chef can either:
- set X := 2 ⋅ X
- or set Y := 2 ⋅ Y
- or set X := X – 1 and Y := Y – 1
Chef is a little busy with preparing the contest. Help him find the minimum number of operations required to make both X and Y equal to 0 simultaneously. If it is impossible to do so after any number of operations, print -1.
Input Format
- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first and only line of each test case contains two space separated integers X and Y.
Output Format
For each test case, print the minimum number of operations required to make X and Y zero simultaneously. If it is impossible to do so after any number of operations, print -1 instead.
Constraints
- 1≤T≤3⋅105
- 0≤X,Y≤1018
Sample 1:
Input
2 1 2 99999999999999999 99999999999999999
Output
3 99999999999999999
Explanation:
SOLUTION
Program: Reduce to zero Solution in Python
for _ in range(int(input())):
x,y=map(int,input().split())
count=max(x,y)
mx=max(x,y)
mn=min(x,y)
if x==y:
print(x)
else:
if mn!=0:
while mn<mx:
mn*=2
count+=1
print(count)
else:
print(-1)Program: Reduce to zero Solution in C++
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t--){
long long int x,y,temp;
cin>>x>>y;
if(x>y){
swap(x,y);
}
if(x==0 && y==0){
cout<<0<<endl;
}
else if(x==0){
cout<<-1<<endl;
}
else{
long long int ans=0;
while(x<y){
x=x*2;
ans++;
}
cout<<ans+y<<endl;
}
}
return 0;
}Program: Reduce to zero Solution in Java
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int t = Integer.parseInt(br.readLine());
while(t-->0){
String s[] = br.readLine().split(" ");
long X = Long.parseLong(s[0]),Y = Long.parseLong(s[1]);
long ans=0;
if(X==Y){
ans = X;
}else if(X==0 || Y==0) ans = -1;
else{
long y = Math.min(X,Y);
long x = Math.max(X,Y);
while(y<x){
y*=2;ans++;
}
y = y/2;ans--;
long begin = y-(x-y);
y = y-begin;
x = x- begin;
ans+=begin;
y*=2;
ans+=x+1;
}
bw.write(ans+"\n");
}
bw.flush();
}
}Related:
