Power Sum POWSUM Solution
You are given a sequence A of N integers such that every element is a non-negative power of 2. A sequence is called good if its sum is a non-negative power of 2. You would like to turn A into a good sequence.
To achieve this, you can perform the following operation on A:
- Pick a non-empty subsequence of A, pick a positive integer X such that X≤230, and multiply every element of this subsequence by X.
Find the minimum number of operations required to turn A into a good sequence. Also, find one sequence of operations which does this. If there are multiple possible answers, you may find any of them.
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.
- The first line of each test case contains a single integer N.
- The second line of each test case contains N space-separated integers A1,A2,…,AN.
Output Format
For each test case, print the answer in the following format:
- First, print one line containing an integer M, denoting the minimum number of moves required.
- Then, print 2M lines describing M operations.
- Each operation is described by 2 lines.
- On the first line, print two space-separated integers K and X, denoting the size of the subsequence and the multiplier for this operation.
- On the second line, print K distinct space-separated integers denoting the indices of the elements chosen to be multiplied in this operation. These K integers can be printed in any order.
Constraints
- 1≤T≤1000
- 1≤N≤100
- 1≤Ai≤220
Subtasks
Subtask #1 (100 points): Original constraints
Sample Input 1
2
4
4 8 4 32
3
2 2 4Sample Output 1
1
3 2
1 2 3
0Explanation
- Test case 1: Multiplying the 1st, 2nd and 3rd elements by 2 turns the array into [8,16,8,32], whose sum is 64=26.
- Test case 2: The array is already
good.
SOLUTION
Program: Power Sum POWSUM Solution in C++
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t--){
int i,n,s=0,j=1,b;
cin>>n;
int a1[n],a2[n];
for(int i=0;i<n;i++){
cin>>a1[i];
a2[i]=a1[i];
s=s+a1[i];
}
sort(a1,a1+n);
b=ceil(log2(s));
auto c=find(a2,a2+n,a1[0]);
j=((pow(2,b)-s)+a1[0])/a1[0];
if((s & s-1)==0){
cout<<0<<endl;
}
else{
cout<<1<<endl;
cout<<1<<" "<<j;
cout<<endl;
cout<<(distance(a2,c))+1<<endl;
}
}
return 0;
}Program: Power Sum POWSUM Solution in Java
import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc=new Scanner(System.in);
int T=sc.nextInt();
for(int t=0;t<T;t++){
int n=sc.nextInt();
int a[]=new int[n];
long sum=0;
for(int i=0;i<n;i++){
a[i]=sc.nextInt();
sum+=a[i];
}
int k= (int) (Math.log10(sum)/Math.log10(2));
if((int)Math.pow(2,k)==sum){
System.out.println(0);
}
else{
long res= (long)(Math.pow(2,++k)) - sum;
for(int i=0;i<n;i++) {
if (res % a[i]==0){
System.out.println(1);
System.out.println(1 +" "+ ((res/a[i])+1));
System.out.println(i+1);
break;
}
}
}
}
}
}Program: Power Sum POWSUM Solution in Python
for _ in range(int(input())):
n = int(input())
arr = list(map(int, input().split(' ')))
upper_value = 1
while upper_value < sum(arr):
upper_value *= 2
s = upper_value - sum(arr) + min(arr)
multiplier = s/min(arr)
if multiplier == 1:
print(0)
else:
print(1)
print(1, int(multiplier))
print(arr.index(min(arr)) + 1)