# Reduce to zero Solution Codechef

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.

• 1≤T≤3⋅105
• 0≤X,Y≤1018

### Sample 1:

Input

```2
1 2
99999999999999999 99999999999999999```

Output

```3
99999999999999999```

## 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
{
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
while(t-->0){
long X = Long.parseLong(s),Y = Long.parseLong(s);
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: