# Sum and OR SUMANDOR Solution Codechef

Page Contents

## 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

Subtask #1 (100 points): Original constraints

```3
13 23
6 13
1 25
```

```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)```