Hello coders, today we are going to solve Mahesh and his lost array CodeChef Solution whose Problem Code is ANUMLA.
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 1Explanation
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.