Sum and OR SUMANDOR Solution Codechef

Sum and OR SUMANDOR Solution

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

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

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

where ∨ denotes the bitwise OR operation.

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

Input Format

  • The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
  • Each test case consists of a single line of input, containing two space-separated integers X and S 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 if no such sequence exists.

Constraints

  • 1≤T≤1000
  • 1≤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 1: One of the valid arrays of length 3 is [9,9,5]. It can be shown that there is no valid array with length <3.
  • Test Case 2: There does not exist any sequence whose sum is 13 and bitwise OR is 6.
  • Test Case 3: The valid array of minimum length contains 25 ones.

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

twelve − seven =