Reduce to zero Solution Codechef

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:

Reduce to zero Solution Explanation
Reduce to zero Solution 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:

Leave a Comment

15 − 1 =