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:
- Subscriptions Solution Codechef
- Alternate Additions Solution Codechef
- Equal Strings Solution Codechef
- Divisible by i Solution Codechef
- Possible GCD Solution Codechef
- Expected move Solution Codechef
- Reduce to zero Solution Codechef
- Full Path Eraser Solution Codechef