Sum and OR SUMANDOR Solution Codechef

Codechef Sum and OR SUMANDOR Solution

Chef has two integers XX and SS. He is interested in sequences of non-negative integers such that the sum of their elements is SS and the bitwise OR of their elements is XX. Chef would like to know the shortest possible length such a sequence can have.

Formally, find the smallest positive integer NN such that there exists a sequence A=[A1,A2,…,AN]A=[A1,A2,…,AN] satisfying the following conditions:

  • Each AiAi is a non-negative integer
  • A1+A2+…+AN=SA1+A2+…+AN=S
  • A1∨A2∨…∨AN=XA1∨A2∨…∨AN=X

where ∨∨ denotes the bitwise OR operation.

If there does not exist any sequence which satisfies the above conditions, output −1−1. Otherwise, output the minimum possible length of such a sequence.

Input Format

  • The first line of input contains a single integer TT, denoting the number of test cases. The description of TT test cases follows.
  • Each test case consists of a single line of input, containing two space-separated integers XX and SS — the required bitwise OR and sum, respectively.

Output Format

For each test case, output a single line containing one integer — the shortest possible length of such a sequence, or −1−1 if no such sequence exists.

Constraints

  • 1≤T≤10001≤T≤1000
  • 1≤X≤S≤1091≤X≤S≤109

Subtasks

Subtask #1 (100 points): Original constraints

Sample Input 1 

3
13 23
6 13
1 25

Sample Output 1 

3
-1
25

Explanation

Test Case 11: One of the valid arrays of length 33 is [9,9,5][9,9,5]. It can be shown that there is no valid array with length <3<3.

Test Case 22: There does not exist any sequence whose sum is 1313 and bitwise OR is 66.

Test Case 33: The valid array of minimum length contains 2525 ones.

Click Below for solution

Solution

Program: Sum and OR SUMANDOR Solution in C++

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

string binaryConversion(int n){
    if(n<2){
        if(n==1)return "1";
        else return "0";
    }
    else{
        if(n%2==1)return "1"+binaryConversion(n/2);
        return "0"+binaryConversion(n/2);
    }
}
int main() {
	int t;
	cin>>t;
	while(t--){
	    int x,s;
	    cin>>x>>s;
	    if(x==s)cout<<1<<endl;
	    else{
	        int ans=s/x;
	        s=s%x;
	        string x1=binaryConversion(x);
	        string s1=binaryConversion(s);
	          reverse(x1.begin(), x1.end());
	       reverse(s1.begin(), s1.end());
	        int l1=s1.length();
	        vector<int> v(l1,0);
	        bool flag=false;
	        for(int i=0;i<s1.length();i++){
	            if(s1[i]=='1'&&x1[x1.length()-s1.length()+i]=='1')v[i]+=1;
	            else if(s1[i]=='1'&&x1[x1.length()-s1.length()+i]=='0'){
	                int j=i;
	                i++;
	                do{
	                    if(x1.length()-s1.length()+i==x1.length()){
	                        cout<<-1<<endl;
	                        flag=true;
	                        break;
	                    }
	                    else{
	                        if(x1[x1.length()-s1.length()+i]=='1'){
	                            v[i]+=pow(2,i-j);
	                            break;
	                        }
	                        else i++;
	                    }
	                    
	                }while(i<=x1.length());
	                i=j;
	            }
	        }
	        if(!flag){
	            sort(v.begin(),v.end(),greater<int>());
	            cout<<ans+v[0]<<endl;
	        }
	    }
	    
	}
	return 0;
}

Program: Sum and OR SUMANDOR Solution in Java

import java.util.*;
class SumOR {
    public static void main(String []args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            int x, s;
            x = sc.nextInt();
            s = sc.nextInt();

            if (s == x) {
                System.out.println(s);
                continue;
            }

            if(s % 2 != 0){
                if((1 & x) == 0){
                    System.out.println("-1");
                    continue;
                }
            }

            boolean []pow2 = new boolean[31];
            Arrays.fill(pow2, false);

            for (int i = 0; i < 31; i++) {
                if ((1 << i & x) != 0) {
                    pow2[i] = true;
                }
            }

            int ans = 0;
            int tot = s;
            int res = Integer.MAX_VALUE;
            tot = tot - x;
            ans++;
            for (int i = 30; i >= 0; i--) {
                if (pow2[i]) {
                    ans = ans + tot / (1 << i);
                    tot = tot % (1 << i);
                }
            }

            res = Math.min(res, ans);
            ans = 0;
            tot = s;
            int rem = x;

            while (tot > 0 && rem > 0) {
                ans = ans + tot / rem;
                tot = tot % rem;

                if (tot == 0) break;

                int sum = 0;
                for (int i = 30; i >= 0; i--) {
                    if (pow2[i]) {
                        if ((sum + (1 << i)) <= tot) {
                            sum += 1 << i;
                        }
                    }
                }
                rem = sum;
            }

            res = Math.min(res, ans);

            if (tot == 0) {
                System.out.println(res);
            } else {
                System.out.println("-1");
            }

        }
    }
}

Program: Sum and OR SUMANDOR Solution in Python

T=int(input())
for i in range(T):
    x,s=map(int,input().split())
    count=0
    if x==1:
        print(s)
    else:
        for j in range(x):
            for k in range(x):
                if (j|k==x):
                    if (j+k==s):
                        count=2
                        break
                    elif (j+k+j==s):
                        count=3
                        break
                    elif (j+k+k==s):
                        count=3
                        break
            if (count>0):
                break
        if (count>0):
            print(count)
        else:
            print(-1)

January Long Challenge 2022 Solution

Leave a Comment

five × one =