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 25Sample Output 1
3
-1
25Explanation
- 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)