Mahesh and his lost array | CodeChef Solution

Hello coders, today we are going to solve Mahesh and his lost array CodeChef Solution whose Problem Code is ANUMLA.

Mahesh and his lost array

Contents

Task

Mahesh got a beautiful array named A as a birthday gift from his beautiful girlfriend Namratha. There are N positive integers in that array. Mahesh loved the array so much that he started to spend a lot of time on it everyday. One day, he wrote down all possible subsets of the array. Then for each subset, he calculated the sum of elements in that subset and wrote it down on a paper. Unfortunately, Mahesh lost the beautiful array :(. He still has the paper on which he wrote all subset sums. Your task is to rebuild beautiful array A and help the couple stay happy 🙂

Input Format

The first line of the input contains an integer T denoting the number of test cases. First line of each test case contains one integer N, the number of elements in A. Second line of each test case contains 2^N integers, the values written on paper.

Output Format

For each test case, output one line with N space separated integers in non-decreasing order.

Constraints

  • 1 ≤ T ≤ 50
  • 1 ≤ N ≤ 15
  • 0 ≤ Values on paper ≤ 10^9
  • All input values are valid. A solution always exists

Example

Sample Input

2
1
0 10
2
0 1 1 2

Sample Output

10
1 1

Explanation

Test case #2 For the array [1,1], possible subsets are {}, {1}, {1}, {1,1}, respective sums are 0, 1, 1, 2.

Solution – Mahesh and his lost array

C++

#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<cstdio>

using namespace std;

#define endl "\n"

#define MOD 1000000007

#define ll long long


int main()
{

#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output2.txt", "w", stdout);
#endif

    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    ll t;
    cin >> t;

    while (t--)
    {

        ll n;
        cin >> n;

        multiset<ll>s, new_s;

        ll i;

        for (i = 0; i < (1 << n); i++)
        {

            ll x;
            cin >> x;
            s.insert(x);

        }

        while (s.size() > 1)
        {

            ll delta = *(++s.begin());

            cout << delta << " ";

            while (s.size())
            {

                multiset<ll>:: iterator i = s.begin();
                ll value_i = *i;

                s.erase(i);

                multiset<ll>:: iterator j = s.find(value_i + delta);
                s.erase(j);

                new_s.insert(value_i);

            }

            s.swap(new_s);

        }

        s.clear();
        new_s.clear();

        cout << endl;

    }

}

Python

from itertools import permutations
from bisect import bisect_left as bl
for __ in range(int(input())):
    n=int(input())
    li=list(map(int,input().split()))
    li.sort()
    li.pop(0)
    t0=[]
    s=[]
    while li:
        t1=[]
        c=li.pop(0)

        for i in t0:
            li.pop(bl(li,c+i))
            t1.append(c+i)
        t1.append(c)
        t0=t0+list(t1)
        s.append(c)

    for i in range(n):
        print(s[i],end=' ')
    print()
        

Java

import java.io.*;
 
import java.util.*;

 class A {
	static FastReader sc=null;
	
	public static void main(String[] args) {
		sc=new FastReader();
		int t=sc.nextInt();
		PrintWriter out=new PrintWriter(System.out);
		while(t-->0) {
			int n=sc.nextInt();
			int a[]=sc.readArray((1<<n));
			int s=(1<<n);
			ArrayList<Integer>ans=new ArrayList<>(),removed=new ArrayList<>();
			TreeMap<Integer,Integer> map=new TreeMap<>();
			for(int i=0;i<s;i++) {
				if(a[i]==0)continue;
				int c=map.getOrDefault(a[i], 0);
				map.put(a[i],++c);
			}
			while(ans.size()<n) {
				//WE REMOVE THE FIRST KEY AND ADD IT TO THE ANSWER
				int c=map.firstKey(),count=map.get(c);
				ans.add(c);
				if(--count>0)map.put(c,count);
				else map.remove(c);
				//THEN WE TRAVERSE THROUGH ALL REMOVED THINGS AND ADD C TO IT AND REMOVE THOSE
				ArrayList<Integer> currRemoval=new ArrayList<>();
				for(int e:removed) {
					int counts=map.get(e+c);
					currRemoval.add(e+c);
					if(--counts>0)map.put(e+c,counts);
					else map.remove(e+c);
				}
				//UPDATE THE REMOVED LIST
				for(int e:currRemoval)removed.add(e);
				removed.add(c);
				//System.out.println(removed.toString());
			}
			for(int e:ans)out.print(e+" ");
			out.println();
			
		}
		out.close();

		
	}
 
	static void reverseSort(int a[]) {
		ArrayList<Integer> al=new ArrayList<>();
		for(int i:a)al.add(i);
		Collections.sort(al,Collections.reverseOrder());
		for(int i=0;i<a.length;i++)a[i]=al.get(i);
	}
	static int gcd(int a,int b) {
		if(b==0)return a;
		else return gcd(b,a%b);
	}
	static long gcd(long a,long b) {
		if(b==0)return a;
		else return gcd(b,a%b);
	}
	static void reverse(int a[]) {
		int n=a.length;
		int b[]=new int[n];
		for(int i=0;i<n;i++)b[i]=a[n-1-i];
		for(int i=0;i<n;i++)a[i]=b[i];
	}
	static void reverse(char a[]) {
		int n=a.length;
		char b[]=new char[n];
		for(int i=0;i<n;i++)b[i]=a[n-1-i];
		for(int i=0;i<n;i++)a[i]=b[i];
	}
	static void ruffleSort(int a[]) {
		ArrayList<Integer> al=new ArrayList<>();
		for(int i:a)al.add(i);
		Collections.sort(al);
		for(int i=0;i<a.length;i++)a[i]=al.get(i);
	}
	
	
	
	static void print(int a[]) {
		for(int e:a) {
			System.out.print(e+" ");
		}
		System.out.println();
	}
	static void print(long a[]) {
		for(long e:a) {
			System.out.print(e+" ");
		}
		System.out.println();
	}
	
	
	static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
        int[] readArray(int n) {
    		int a[]=new int [n];
    		for(int i=0;i<n;i++) {
    			a[i]=sc.nextInt();
    		}
    		return a;
    	}
        long[] readArrayL(int n) {
    		long a[]=new long [n];
    		for(int i=0;i<n;i++) {
    			a[i]=sc.nextLong();
    		}
    		return a;
    	}
    } 
}

Disclaimer: The above Problem (Mahesh and his lost array) is generated by CodeChef but the Solution is Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.

Leave a Comment

Your email address will not be published.