Help me in solving XORRY2 problem

help
,
1

My issue

plz give hint ,how to start this question

My code

import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
	 Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();

        for (int i = 0; i < t; i++) {
            int x = scanner.nextInt();
           int a=  findA(x);
            //int b = x ^ a;
            System.out.println(a);
        }
    }

    private static int findA(int x) {
        int ans1=Integer.MAX_VALUE;
         int a = 0;
        for (int i = 30; i >= 0; i--) {
            if ((a | (1 << i)) <= x && ((a | (1 << i)) ^ x) >= a) { // Ensure (b - a) is minimized
                a |= (1 << i);
                ans1=Math.min(ans1,(a-(a^x)));
            //   System.out.println(ans1);
            }
        }
        int ans=0,res=0;
         for (int i = 30; i >= 0; i--) {
            if ((ans | (1 << i)) <= x && ((ans | (1 << i)) ^ x) >= ans) { // Ensure (b - a) is minimized
                ans |= (1 << i);
               if(ans1==(ans-(ans^x))){
                   res++;
               }
            }
           
        }
        return res;
    }
	
}

Problem Link: Xorry 2 Practice Coding Problem - CodeChef

2

@deepak_5047
heyy , plzz refer my c++ code for better understanding of the logic

#include <bits/stdc++.h>
using namespace std;

int main() {
	// your code goes here
	int t;
	cin>>t;
	while(t--)
	{
	    long long int n;
	    cin>>n;
	    long long int p=1,ch=0,cnt=0,cnt1=0;
	    while(p<=n)
	    {
	        long long int val=p&n;
	        if(val==p)
	        {
	            ch=p;
	        }
	        
	        p=p*2;
	    }
	    p=1;
	    n-=ch;
	    while(p<=n)
	    {
	        long long int val=p&n;
	        if(val!=p)
	        cnt++;
	        p=p*2;
	    }
	        long long int ans=1;
	        for(int i=0;i<cnt;i++)
	        {
	            ans=ans*2;
	        }
	        cout<<ans;
	    cout<<endl;
	}

}
4

thanks .

5

your code is not understandable for someone who doesn’t know the logic. You have just provided the code and haven’t described the logic behind it.

6

Intuition: First of all you have to think about the logic if you have done the xory1 question then it is better to proceed and bit manipulation is must for this question.

if you have done the xory1 question then you know that we cannot alter the existing ones present in the number(binary form) as all the ones have to be converted into zero except the first. so we have the choice on the zeros after the second one. We can make them zero or one to form the different pairs. And that is what we are doing here.

#include <bits/stdc++.h>
using namespace std;

string covert_to_binary(int x){
    string ans = ""; 
    
    while(x > 0){
    	ans = ((x%2)? '1' : '0') + ans;
        x >>= 1;
    }
    
    return ans; 
}

int pos_of_second_one(string bin){
	int count = 0; 

	for(int i=0; i<bin.size(); i++){
		if(bin[i] == '1') count++;
		if(count == 2) return i;
	}

	return -1; 
}

int no_of_zeros_after_second_one(string bin, int ind){
	if(ind == -1) return 0; 
	int count = 0; 

	for(int i = ind; i<bin.size(); i++){
		if(bin[i] == '0') count++; 
	}

	return count ;
}

void solve(){
	int x ; cin>>x; 

	string bin = covert_to_binary(x) ;
	int ind = pos_of_second_one(bin) ;
	int count = no_of_zeros_after_second_one(bin, ind); 

	int ans = 1<<count;   // don't be afraid of this line it is just a simple way to calculate paw(2, count)
	cout<<ans; 
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve(); 
        cout<<endl;
    }
    return 0;
}

Please provide a feedback if you got it or not :blush: :blush:.

1 Like
7

Got it .