Power Sum POWSUM Solution Codechef

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

Subtasks

Subtask #1 (100 points): Original constraints

Sample Input 1 

2
4
4 8 4 32
3
2 2 4

Sample Output 1 

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)

January Long Challenge 2022 Solution

Leave a Comment

14 + 4 =