# Power Sum POWSUM Solution Codechef

Page Contents

## Codechef Power Sum POWSUM Solution

You are given a sequence AA of NN integers such that every element is a non-negative power of 22.

A sequence is called `good` if its sum is a non-negative power of 22. You would like to turn AA into a `good` sequence.

To achieve this, you can perform the following operation on AA:

• Pick a non-empty subsequence of AA, pick a positive integer XX such that X≤230X≤230, and multiply every element of this subsequence by XX.

Find the minimum number of operations required to turn AA 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 TT, denoting the number of test cases. The description of TT test cases follows.
• The first line of each test case contains a single integer NN.
• The second line of each test case contains NN space-separated integers A1,A2,…,ANA1,A2,…,AN.

### Output Format

For each test case, print the answer in the following format:

• First, print one line containing an integer MM, denoting the minimum number of moves required.
• Then, print 2M2M lines describing MM operations.
• Each operation is described by 22 lines.
• On the first line, print two space-separated integers KK and XX, denoting the size of the subsequence and the multiplier for this operation.
• On the second line, print KK distinct space-separated integers denoting the indices of the elements chosen to be multiplied in this operation. These KK integers can be printed in any order.

### Constraints

• 1≤T≤10001≤T≤1000
• 1≤N≤1001≤N≤100
• 1≤Ai≤2201≤Ai≤220

Subtask #1 (100 points): Original constraints

```2
4
4 8 4 32
3
2 2 4
```

```1
3 2
1 2 3
0
```

### Explanation

Test case 11: Multiplying the 1st,2nd1st,2nd and 3rd3rd elements by 22 turns the array into [8,16,8,32][8,16,8,32], whose sum is 64=2664=26.

Test case 22: The array is already `good`.

Click Below for solution

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