PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Setter: Utkarsh Gupta
Tester: Taranpreet Singh
Editorialist: Kanhaiya Mohan
DIFFICULTY:
Easy-Medium
PREREQUISITES:
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];
vector <int> adj[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 readString(int l,int r,char endd){
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){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
void solve()
{
ll x=readInt(1,1000000000,' ');
ll s=readInt(x,1000000000,'\n');
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[35]={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=readInt(1,1000,'\n');
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;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
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());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}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[0]<=m;
return sum[0]==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;
}
