 # SUMANDOR - Editorial

Setter: Utkarsh Gupta
Tester: Taranpreet Singh
Editorialist: Kanhaiya Mohan

Easy-Medium

# PROBLEM:

Given two integers X and S, find the length of the smallest sequence such that:

• All the elements of the sequence are non-negative integers.
• Sum of all the elements of the sequence is S.
• Bitwise Or of all the elements of the sequence is X.

# QUICK EXPLANATION:

• One element of the sequence is X.
• We will do a binary search for the length of the sequence. Let the current value of length be m. We will have m copies of each (set) bit.
• Since one element of the sequence is X, we need to find a sequence of length (m-1) with sum (S-X) and bitwise or equal to Y (Y∨X = X).
• Traverse the bits of X from highest bit to lowest bit (not including the lowest bit).
• If the i^{th} bit of X is 0, transfer all copies of set bits of (S-X) to next bit. If it is 1, transfer all excess copies to the next bit.
• If the lowest bit of X is 0, there should be no copies of set bits for the lowest bit in (S-X). If it is 1, there should be atmost (m-1) copies.
• If there is no value of m between 1 and 10^9 which satisfies the given conditions, the answer is -1.

# EXPLANATION:

X is one of the elements of the sequence: Considering the binary representation of X, we want to find a sequence of integers A of length N such that:

• If the i^{th} bit of X is 0, the i^{th} bit of A_i is 0 for all 1 \leq i \leq N.
• If the i^{th} bit of X is 1, the i^{th} bit of A_i is 1 for at least one 1 \leq i \leq N.

We know that the sum of elements S \geq X. To fulfill the second condition, we can simply have X as one of the elements of the sequence.

Binary Search over the length of sequence: Suppose that a length N satisfies the given conditions.
What about length (N+1) ? We can simply add a 0 to the previous sequence of length N. Thus, length (N+1) would also satisfy all conditions.
What about length (N-1) ? We cannot say for sure if we can generate a sequence of length (N-1) satisfying all conditions based on the given result of length N. Thus, we would have to check again.

Sounds familiar? We can apply binary search on the length of the sequence. If the current length m satisfies all conditions, we look for a smaller value of length, else, we look for a greater value of length.

Lower and Upper Bound

Lower Bound: If S=X, we need only one element in the sequence that is X itself. Thus, the lower bound is 1.
Upper Bound: Consider the case when S takes the maximum value i.e. 10^9 and X takes the minimum value i.e. 1. We need a sequence of 10^9 elements where the value of each element is 1. Thus, the upper bound is 10^9.

If no possible m exists between lower and upper bound, the answer is -1.

Check function of binary search: We need to determine if a sequence of length m can have sum of elements equal to S and bitwise or of elements equal to X.

If we are given a length m, each (set) bit can have m copies. Since one of the elements is X, we have m-1 copies left for each set bit.
Our problem reduces to finding a sequence of length (m-1) with sum (S-X) and bitwise or equal to Y (Y∨X = X).

We traverse the bits of X from highest bit to lowest bit (not including the lowest bit). Consider the i^{th} bit:

• i^{th} bit of X is 0: This means that there should be no copies of set bits for the i^{th} bit in (S-X). If there are any, we can transfer these to the (i+1)^{th} bit of (S-X) (by multiplying with a factor of 2).
• i^{th} bit of X is 1: There can be at most (m-1) copies of set bits for the i^{th} bit in (S-X). All excess copies can be transferred to the (i+1)^{th} bit of (S-X) (by multiplying with a factor of 2).

For the lowest bit:

• Lowest bit of X is 0: If there are any copies of set bits for the lowest bit in (S-X), sequence of length m does not exist, else it exists.
• Lowest bit of X is 1: If the number of copies of set bits for the lowest bit in (S-X) exceeds (m-1), sequence of length m does not exist, else it exists.

# TIME COMPLEXITY:

The time complexity is O(log(10^9)\cdot log(10^9)) which is O(1) for each test case.

# SOLUTION:

Setter's Solution
//Utkarsh.25dec
#include <bits/stdc++.h>
#include <chrono>
#include <random>
#define ll long long int
#define ull unsigned long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define rep(i,n) for(ll i=0;i<n;i++)
#define loop(i,a,b) for(ll i=a;i<=b;i++)
#define vi vector <int>
#define vs vector <string>
#define vc vector <char>
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define deb(x) cerr<<#x<<' '<<'='<<' '<<x<<'\n'
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// ordered_set s ; s.order_of_key(val)  no. of elements strictly less than val
// s.find_by_order(i)  itertor to ith element (0 indexed)
typedef vector<vector<ll>> matrix;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
/*
------------------------Input Checker----------------------------------
*/

long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);

assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}

if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}

return x;
} else {
assert(false);
}
}
}
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
}
long long readIntLn(long long l,long long r){
}
}
}
void solve()
{
s-=x;
ll ans=1;
if(s==0)
{
cout<<ans<<'\n';
return;
}
ll l=1,r=1e9;
while(l<=r)
{
ll mid=(l+r)/2;
ll cnt={0};
for(int i=30;i>=0;i--)
{
if((x&(1<<i))!=0)
cnt[i]=mid;
}
int flag=1;
for(int i=30;i>=0;i--)
{
if((s&(1<<i))==0)
continue;
ll req=1;
int j;
for(j=i;j>=0;j--)
{
if(cnt[j]>=req)
{
cnt[j]-=req;
break;
}
else
{
req-=cnt[j];
cnt[j]=0;
req*=2;
}
}
if(j==-1)
flag=0;
}
if(flag)
r=mid-1;
else
l=mid+1;
}
if(l>1000000000)
cout<<-1<<'\n';
else
cout<<l+1<<'\n';
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t=0;
while(t++<T)
{
//cout<<"Case #"<<t<<":"<<' ';
solve();
//cout<<'\n';
}
assert(getchar()==-1);
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

Tester's Solution
import java.util.*;
import java.io.*;
class SUMANDOR{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
long X = nl(), S = nl();
long D = S-X;
long B = X^(X&(X-1));
if(D%B != 0){
pn(-1);
return;
}
int lo = 1, hi = (int)1e9+1;
while(lo < hi){
int mid = lo + (hi-lo)/2;
if(possible(X, S, mid))hi = mid;
else lo = mid+1;
}
hold(hi <= 1e9);
pn(hi);
}
boolean possible(long X, long S, int cnt) throws Exception{
long sum = S-X;
cnt--;
int B = 30;
for(int b = B-1; b>= 0; b--){
if(((X>>b)&1) == 0)continue;
long times = Math.min(cnt, sum/(1L<<b));
sum -= times*(1L<<b);
}
return sum == 0;
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
void run() throws Exception{
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new SUMANDOR().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}

StringTokenizer st;
}

}

String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
}catch (IOException  e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}

String nextLine() throws Exception{
String str = "";
try{
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}

Editorialist's Solution
#include <bits/sdc++.h>
using namespace std;

#define sync {ios_base ::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}
#define rep(n) for(int i = 0;i<n;i++)
#define rep1(a,b) for(int i = a;i<b;i++)
#define int long long int
#define mod 1000000007

bool possible(int x, int s, int m){
vector<int> sum(30, 0);
for(int i = 29; i>=0; i--){
if((s>>i)&1) sum[i] = 1;
}

for(int i = 29; i>=1; i--){
if((x>>i)&1){
if(sum[i]>m)
sum[i-1] += 2*(sum[i]-m);
}
else{
sum[i-1] += 2*sum[i];
}
}

if(x&1)
return sum<=m;
return sum==0;
}

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

s -= x;

int l = 1, r = 1e9+1;
while(l<r){
int m = l + (r-l)/2;
if(possible(x, s, m-1)){
r = m;
}
else{
l = m+1;
}
}
if(r>1e9) r = -1;
cout<<r;
}

int32_t main()
{

#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif

sync;
int t = 1;
cin>>t;
while(t--){
solve();
cout<<"\n";
}
return 0;
}

5 Likes

https://www.codechef.com/viewsolution/56545275
For which test case did it fail? I took the set bits and formed the largest num possible and kept doing it till the sum is 0 or num is 0
During the contest, I was trying this solution and I was not able to find the edge case for it Instead of initializing right from 1e9+1 we can do S+1, since that’s the max no. of 1s we can use. will reduce additional complexity per test case.

2 Likes

I hate bitwise question. Just don’t know how to solve them.

1 Like

Yeah. Right.

Solution: 56488894 | CodeChef
why it’s giving the wrong ans!!. I just iterated over the submasks of x and checked the sum in decreasing order…

Did you get for which cases this approach is wrong?
kishu_123 I was also trying the same method and till now I am not able to get what is wrong with the approach input :
1
10 26
expected output :
3

1 Like

Solution: 56574615 | CodeChef
can someone help

According to the constraints X\leq S.

1 Like

Easy to fall in the trap of Greedy Strategy and that is the driving factor behind the accuracy

1 Like

#include<bits/stdc++.h>

using namespace std;
#define ll long long

void solve(int x, int s) {
if(s<x || !(s-x)%(x&(-x))) cout << “-1\n”;
else if (s==x) cout << “1\n”;
else {
if(x==1) cout << s << “\n”;
else {
int ls, mx = 0;
while(x) {
ls = 1<<(int)(log2(x));
mx = max(mx, s/(ls));
x -= ls;
s -= ls*(s/ls);
}
if(s) cout << “0\n”;
else cout << mx << “\n”;
}
}
}

int main() {
int test;
cin >> test;

while(test--) {
int x, s;
cin >> x >> s;

solve(x, s);
}


}

depressedboy Yes Greedy Strategy doesn’t work in this case as for:

input :
1
10 26
expected output :
3 (i.e 10 + 8 + 8 )
My Output:
5 (i.e 10 + 10 + 2 + 2 + 2)


A Silly Question , how to know that greedy doesn’t work?

There is no particular way to know it . Either I was also trying greedy solution .
You can try some counter testcases to your current solution such that this testcases will fail your solution to see if greedy works or not .

CAN SOMEONE PLEASE HELP ME WHY THIS CODE IS NOT WORKING WHAT WAS THE MISTAKE I WAS DOING ??

#include<bits/stdc++.h>

#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

using namespace std;

#define ll long long

vector con_to_binary(ll x){

stack<ll>s;

while (x>0)

{

s.push(x%2);

x/=2;

}

vector<ll>v;

while (!s.empty())

{

v.push_back(s.top());

s.pop();

}

return v;


}

signed main()

{

fast;

ll tc;

cin>>tc;

while(tc--)

{

ll x,s;

cin>>x>>s;

if(x==1){

cout<<s<<"\n";

}

else {

vector<ll>v;

vector<pair<ll,ll>>ans;

v=  con_to_binary(x);

ll tt=s;

for (ll i =0; i <v.size(); i++)

{

if(v[i]==1){

ll k=v.size()-1-i;

//   cout<<k<<" ";

ll t=pow(2,k);

ans.push_back({s/t,k});

s%=t;

}

}

ll sum=0;

for (ll i = 0; i < ans.size(); i++)

{

sum+=ans[i].first*pow(2,ans[i].second);

}

// cout<<sum<<"\n";

if(sum==tt){

cout<<ans.size()<<"\n";

}

else{

cout<<"-1\n";

}

}

}


return 0;

}