POWSUM - Editorial

Setter: Prasant Kumar
Tester: Taranpreet Singh
Editorialist: Kanhaiya Mohan

Easy

PREREQUISITES:

Binary Representation

PROBLEM:

You are given a sequence of A on N integers such that every element is a non-negative power of 2. A sequence is called \text{good} if its sum is a non-negative power of 2. Find the minimum number of operations required to turn A into a \text{good} sequence.

An operation is defined as: Pick a non-empty subsequence of A, pick a positive integer X (X \leq 2^{30}), and multiply every element of this subsequence by X.

Find any sequence of minimum operations that turns A into \text{good} sequence.

QUICK EXPLANATION:

• Required number of operations is either 0 or 1.
• If the sequence is not \text{good}, we require only 1 operation.
• Let S be the sum of the sequence (where S is not a power of 2) and r be the smallest integer such that S < 2^r. In one operation, we choose the smallest number of the sequence (M), and multiply it with X = \frac{2^r - (S - M)}{M}.

EXPLANATION:

If the sequence is already \text{good}, we need 0 operations.

If the sequence is not \text{good}, we can make it good using exactly one operation. How?
Let S be the sum of the sequence. We know that S is not a power of 2. After some number of operations, let us assume that we achieve a sum of 2^r, thus, making the sequence \text{good}.
S>2^r: This is because, in each operation we multiply some subsequence with a positive integer. This would increase the value of the elements of that subsequence and thus the overall sum.
This means that we have to increase S at least to 2^r such that 2^{r-1} < S <2^r. For this, we need to add 2^r - S to the sequence.
Let M denote the smallest element of the sequence.

Claim: 2^r - S is a multiple of M.
Proof: An important thing to note is that all numbers of the sequence are powers of 2.

Let p be the number of trailing zeroes in the binary representation of M (M = 2^p) and q be that of S. Also, the number of trailing zeroes in the binary representation of 2^r is r. Since M is the smallest element of the sequence, p \leq q. Similarly, since 2^r>S, r>q.
This means that the number of trailing zeroes in the binary representation of 2^r-S is also q.

A binary number with q trailing zeroes is divisible by 2^q. This implies that 2^r-S is divisible by 2^q. Also, since p\leq q, 2^r-S is divisible by 2^p, which is nothing but M. Hence proved, 2^r-S is divisible by M.

To convert S to 2^r, we can simply multiply M by \frac{2^r - (S - M)}{M}. This would take only one operation and make the sum of sequence equal to 2^r. The chosen subsequence in the operation only consists of M.

TIME COMPLEXITY:

We have to traverse the array to find the minimum element and the sum of elements. Thus, the time complexity is O(N) per test case.

SOLUTION:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int sf=2e5+10; // size for fac and inverse fac.
int M=1e9+7; // modulus, change it if different.
// dont copy others template you will get plagiarized.
int fac[sf],invFac[sf];
int power(int a,int b){
int ans=1;
while(b>0){
if(b&1){
ans*=a;
ans%=M;
}
a*=a;
a%=M;
b/=2;
}
return ans;
}
int findInv(int a){
return power(a,M-2);
}
void preFac(){ // pre process
fac[0]=invFac[0]=1;
for(int i=1;i<sf;i++){
fac[i]=(fac[i-1]*i)%M;
invFac[i]=findInv(fac[i]);
}
}
int nCr(int n,int r){  // call only if preprocess is done
return ((fac[n]*invFac[r])%M * invFac[n-r])%M;
}
int msb(int n){ // change 63 to 31 if 32 bit integer is used and use __builtin_clz(n)
return 63 - __builtin_clzll(n);
}

// => pre-process
// => change size of array, modulus if required.
// -------------------------------------------------------------------------------------------------------------------------------------------

signed main(){
ios_base::sync_with_stdio(0) , cin.tie(0);
int t;cin>>t;
while(t--){
int n;cin>>n;
int mini=1e9,ind;
int sum=0;
int arr[n];
for(int i=0;i<n;i++){
cin>>arr[i];
if(arr[i]<mini){
mini=arr[i];
ind=i;
}
sum+=arr[i];
}
if((sum&(sum-1))==0){
cout<<0<<endl;
}else{
int next=1ll<<(msb(sum)+1);
int dif=next-sum;
cout<<1<<endl;
cout<<1<<" "<<(dif/mini + 1)<<endl;
cout<<ind+1<<endl;
}
}
return 0;
}

Tester's Solution
import java.util.*;
import java.io.*;
class POWSUM{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni();
int[] A = new int[N];
for(int i = 0; i< N; i++)A[i] = ni();
int sum = 0;
for(int x:A)sum += x;
if((bit(sum)) == 1)pn(0);
else{
pn(1);
int total = (Integer.highestOneBit(sum)<<1)-sum;
for(int i = 0; i< N; i++){
if(total%A[i] == 0){
pn("1 "+(total/A[i]+1));
pn(1+i);
return;
}
}
hold(false);
}
}
//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 POWSUM().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/stdc++.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

int n;

void solve()
{
cin>>n;
int a[n];

int sum = 0;
int minm = INT_MAX;
int min_index = 0;
for(int i = 0; i<n; i++){
cin>>a[i];
if(minm > a[i]){
minm = a[i];
min_index = i+1;
}
sum += a[i];
}

if((sum & (sum-1)) == 0){
cout<<0;
return;
}

int no_of_bits = (int)log2(sum) + 1;
int target = 1<<no_of_bits;
int needed = target - (sum - minm);
int x = needed/minm;
cout<<1<<endl;
cout<<1<<' '<<x<<endl;
cout<<min_index;
}

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;
}
9 Likes

great explanation

1 Like

A more interesting, and difficult, problem is to identify a subsequence to achieve the desired result with a minimum multiplying factor. Short of brute force, I do not know to solve this alternative problem.

1 Like

how to think that it could be only in one step ?

1 Like
#include<bits/stdc++.h>
using namespace std;
//fors
#define loop(i,b) for(int i=0;i<b;i++)
#define ones(n)   __builtin_popcount(n)

main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int ar[n];
int mn = 1e9,sum=0,ind=-1;
loop(i,n){
cin>>ar[i];
if(mn>ar[i]){
ind = i;
mn = ar[i];
}
sum+=ar[i];
}
if(ones(sum)==1){
cout<<0;
}
else{
sum -= mn;
int pw = log2(sum) + 1;
int x = (pow(2,pw) -sum)/mn;
cout<<1<<"\n"<<1<<" "<<x<<"\n"<<ind;
}
cout<<"\n";
}
cerr<<"time taken: "<<(float)clock()/CLOCKS_PER_SEC<<endl;
}

Can anybody tell me whats wrong with this ?
What I am doing here is saying if the sum is not a power of 2 then I am just taking the minimum element from the array and multiplying it by the required amount to make it a power of 2

hii, you are calculating the value of x worng , you are forgetting the min element that is already present in the sequence. You can figure it outâ€¦ I Think.

and use long long

And well i subtracted the min element(sum -= mn) and long long wouldâ€™nt be necessary because the sum would never reach it a[i] <= 2^20 and n= 100 that means 10485760 is max the sum could go which is much less than the limit of int

Well I got it while printing the index i was assuming 0 based indexing but we have to use 1 based indexing.

Can you please explain this with a test case. Not able to get the point.

1st Sample test case output must be :

1
1 5
1