CareerCup

The idea is simple. If the ordering of sums is known, we can easily reconstruct the array. Given the P array, calculate N (no. of elements in S).
Then observe,

S[0] = (P[0] + P[1] - P[n - 1]) / 2

Why?

P[0] = S[0]+S[1], P[1]=S[0]+S[2], P[n - 1] = S[1]+S[2]

Now run a loop to calculate the rest.

Code in Java:

int[] getOriginalArray(int[] P, int n) {
	int[] S = new int[n];
	S[0] = (P[0] + P[1] - P[n - 1]) / 2;
	for (int i = 1; i < n; i++) {
		S[i] = P[i] - S[0];
	}
	return S;
}

@emb. Could you give more explanation about the question with an example? Especially the 'note' part you have specified.

-Thanks

given: pairwise sum set, set of numbers
solution-
1- calculate the pairwise sum from set of numbers- nC2
2- get pairwisesum - nC2 such that the answer is numbers in pairwisesum but not in nC2 solution
3- for each number from resultset of 2, subtract each number from set of numbers to get a set of new numbers.

assumption- anything new sum we find in pairwise sum which cannot be achieved from given set can result in n number of values by subtracting n set values from set of numbers

The naive solution could be something like the following:

def nextPeer(sortedItems, cval, sum, k):
        while k < len(sortedItems) :
              z = cval + sortedItems[k]
              if z == sum :
                      return k  
              else:
                      k += 1  
        return -1

def findPeer(sortedItems, sum, p1):
        while p1 < len(sortedItems):
             cval = sortedItems[p1]
             p2 = nextPeer(sortedItems, cval, sum, p1+1) 
             
             if p2 == -1:
                p1 += 1
             else:
                return (p1, p2)

        return (-1, -1)   
def myPair(xSet, sumSet):

    pairs = dict()
 
    sorted_x_set = sorted(xSet, key = lambda x: x, reverse = True)  
    sorted_sum_set = sorted(sumSet, key = lambda x: x, reverse = True)
    

    for s in sorted_sum_set:
        j = 0 
        while sorted_x_set[j] >  s :
             j+= 1
        (peer1, peer2) = findPeer(sorted_x_set, s,j) 
        if peer1 != -1 and peer2 != -1:
             pairs[s] = (sorted_x_set[peer1], sorted_x_set[peer2])
                   
    print(sorted_sum_set)
    print(sorted_x_set)
    for p in pairs:
        print(p, '::', pairs[p]) 

x = [2, 3, 4, 7,20,9]
z = [5, 11, 7, 6, 10, 9,23, 29,15,29]
myPair(x,z)

Sample Output:::
[29, 29, 23, 15, 11, 10, 9, 7, 6, 5]
[20, 9, 7, 4, 3, 2]
5 :: (3, 2)
6 :: (4, 2)
23 :: (20, 3)
7 :: (4, 3)
9 :: (7, 2)
10 :: (7, 3)
11 :: (9, 2)
29 :: (20, 9)
If multiple pairing are possible, this program will only generate one of them!

Here is the fundamental idea.. I could be wrong and I am not writing the code.. just the idea.. (It takes the assumption that pairwise sums will be in order)

How many pairwise sums will there be for n terms?
For 3 terms, pairwise sums will be 2 + 1
for 4 terms, pairwise sums will be 3 + 2 + 1
so for n, the relation will come out as n - 1 + (n - 2) + ... + 1

now that you have the above, we can find n using pairwise sums set by incrementing i, adding it to current sum and that should equal the length of given array.

After that, term 1 is x1 + x2, term 2 is x1 + x3 and term n will be x2 + x3.

Compute term 1 + term 2 - term n -> This will be x1 + x2 + x1 + x3 - x2 - x3 = 2 * x1
div by 2 to get x1.
once you have x1, just subtract that from numbers till terms n - 1 for getting other terms.

x2 can be computed as x1 + x2 - x1 and so on. You will get all terms in n.

Can we assume than numbers are different?

Could you explain what is given - sum of pairs or sum of pairs and numbers in the beginning. Initally I tought that we have only sum of pair of numbers and should find numbers in these sums, without having then in advance, but after I had a look on the proposed solutions , I noticed that you assume that you have numbers and their sum in unordered way and has to guess which numbers belongs to which sum. Please explain better

For a0 = 1, till max_value a[0] could be (there is a constraints on the sums) try to generate all numbers taking into the account the current minimum sum. Each time we add new number we generate all sums of given number and previously added numbers and check if these sums actually exists, if not we try with another a[0] (first) number. If all sums exists we generate next number as difference between current minimum sum and a[0].

If we assume that we know order of sums in P, we can do it as follows:
n = no. of elements in S. To be calculated based on size of P. Simple quadratic equation solver.
s[0]=(p[0]+p[1]-p[n-1])/2
Why? Because:
p[0]=s[0]+s[1]
p[1]=s[0]+s[2]
p[n-1]=s[1]+s[2]

Now run a loop and you're done.
Code in Java:

public int[] reconstruct(int[] p, int n) {
	int[] s = new int[n];
	s[0] = (p[0]+p[1]-p[n-1])/2;
	for (int i = 1; i < n; i++) {
		s[i]=p[i]-s[0];
	}
	return s;
}

How about this, and thanks for the above suggestions.

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>

int P[] = { 6, 11, 101, 15, 105, 110 };
void getElementsofS(int P[], int size) {
	int *S = (int*)calloc(sizeof(int)*size, 1);
	assert(S != NULL);
	S[0] = (P[0] + P[1] - P[size - 1]) / 2;
	printf("S = %d ", S[0]);
	for (int i = 1; i < size; i++) {
		printf("%d ",S[i] = P[i - 1] - S[0]);
	}
}
int fact(unsigned int n){
	if (n == 1) return 1;
	return n * fact(n - 1);
}
int main(){
	int i = 3;
	int maxSize = (sizeof(P) / sizeof(P[0]));
	for (; i < maxSize; i++){
		if (fact(i - 1) == maxSize)
			break;
	}
	if (i == maxSize){
		printf("Array P is not of set Rule\n");
		return 0;
	}
	getElementsofS(P, i);
	return 0;
}

This solution is very close to what Diptesh has mentioned.
Posting it in C.
O(n) time complexity

First we need to determine the size of the S array.
We will be solving for P length = n*(n-1)/2
Which is x*y = 2*len(P) && x-y = 1 where x is the length of S.
We will also use the length to compute each entry in S.
eg.
P = {x1+x2, x1+x3, ...., x2+x3}
adding first 2 and subtracting the first sum of the next element.
2x1+x2+x3-(x2+x3) = 2x1
We will do this until we hit the last element in the P. Which is the only sum for last two elements in S.
Special case for the last two elements in S.
We will use the last two sums to compute P[i-2] & P[i-1] and subtract the known last element.
eg.
P = {....x2+x3,x2+x4,x3+x4}
So far our S computed will be
S = {x1,x2}
So we will subtract last known element from the last two sums
x2+x3 - x2 = x3
&&
x2+x4 - x2 = x4

#include <stdio.h>

int find_length_from_sum(int sum_set_length) {
	int other_factor;
	for (int i = 0; i < sum_set_length/2; ++i)
	{
		if ((2*sum_set_length) % i)
		{
			other_factor = (2*sum_set_length) / i;
			if (other_factor - i == 1)
			{
				return other_factor;
			}
		}
	}
	return 0;
}

int find_value(int current_index, int next_offset) {
	int 2x1_x2_x3 = P[current_index] + P[current_index+1];
	int x2_x3 = p[current_index + next_offset - 1];
	int 2x1 = 2x1_x2_x3 - x2_x3;
	int x1 = 2x1/2;
	return x1;
}

int main(int argc, char const *argv[])
{
	int length = find_length_from_sum(P.length);
	int S[length];
	int current_index = 0;
	int next_offset = length;
	for (int i = 0; i < length && current_index < P.length; ++i)
	{
		S[i] = find_value(current_index, next_offset);
		current_index = current_index + next_offset - 1;
		next_offset = next_offset - 1;
	}
	S[i+1] = P[current_index-2] - S[i];
	S[i+2] = P[current_index-1] - S[i];
	return 0;
}

Running Time O(n)
Additional space O(n)

import java.util.ArrayList;
import java.util.HashMap;

public class arrayelements {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
int[] parray={6,11,101,15,105,110};
HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
ArrayList<Integer> array=new ArrayList<Integer>();
int n=0,index=0,sum=0;
n=method(parray);
int pos=n;
while(n>0)
{sum=0;
	for(int i=index;i<(index+n);i++)
sum+=parray[i];	
map.put(n, sum);
index+=n;
n--;
}
int first=0,prev=0;
for(int k=2;k<=pos;k++)
{
	first= (map.get(k)-(map.get(k-1)-prev))/k;
	prev=first;
}
array.add(first);
for(int i=0;i<pos;i++)
	array.add(parray[i]-first);
System.out.println(array);
	}

	private static int method(int[] parray) {
		// TODO Auto-generated method stub
		for(int i=1;i<=parray.length/2;i++)
		{
			if(i*i+i == (parray.length*2) )
				return i;
		}
	return -1;
	}
}

import java.util.ArrayList;
import java.util.HashMap;

public class arrayelements {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
int[] parray={6,11,101,15,105,110};
HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
ArrayList<Integer> array=new ArrayList<Integer>();
int n=0,index=0,sum=0;
n=method(parray);
int pos=n;
while(n>0)
{sum=0;
	for(int i=index;i<(index+n);i++)
sum+=parray[i];	
map.put(n, sum);
index+=n;
n--;
}
int first=0,prev=0;
for(int k=2;k<=pos;k++)
{
	first= (map.get(k)-(map.get(k-1)-prev))/k;
	prev=first;
}
array.add(first);
for(int i=0;i<pos;i++)
	array.add(parray[i]-first);
System.out.println(array);
	}

	private static int method(int[] parray) {
		// TODO Auto-generated method stub
		for(int i=1;i<=parray.length/2;i++)
		{
			if(i*i+i == (parray.length*2) )
				return i;
		}
	return -1;
	}

}

import java.util.ArrayList;
import java.util.HashMap;

public class arrayelements {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
int[] parray={6,11,101,15,105,110};
HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
ArrayList<Integer> array=new ArrayList<Integer>();
int n=0,index=0,sum=0;
n=method(parray);
int pos=n;
while(n>0)
{sum=0;
	for(int i=index;i<(index+n);i++)
sum+=parray[i];	
map.put(n, sum);
index+=n;
n--;
}
int first=0,prev=0;
for(int k=2;k<=pos;k++)
{
	first= (map.get(k)-(map.get(k-1)-prev))/k;
	prev=first;
}
array.add(first);
for(int i=0;i<pos;i++)
	array.add(parray[i]-first);
System.out.println(array);
	}

	private static int method(int[] parray) {
		// TODO Auto-generated method stub
		for(int i=1;i<=parray.length/2;i++)
		{
			if(i*i+i == (parray.length*2) )
				return i;
		}
	return -1;
	}

}

my working php solution
time complexity : O( (n * (n-2)) + 3 + n) with helper variables.
memory: almost same with time complextiy.
space complexity :

function getSublistSize($length)
{
    $i = 2;
    $n = 0;

    while ($i <= $length) {
        if (is_int($length / $i)) {
            if ($length == $i * ($i + 1) / 2) {
                return ($i + 1);
            }
        }

        ++$i;
    }

    return $n;
}

function findSubstractList(array $list)
{
    $length = count($list);

    $n = getSublistSize($length);
    $nth = $n - 1;

    $substractList = [];
    $substractTotal = array_sum($list) / ($length / 2); // A + B + C + D

    /**
     * formula : A = (list[0] + list[1] - list[nth -1]) / 2
     * list[0] = A + B,
     * list[1] = A + C,
     * list[nth - 1] = B + C
     *
     * =>  ((A + B) + (A + C) - (B + C)) / 2
     * => (A + A + (B + C - B - C)) / 2
     * => (2A + 0) / 2 => 2A / 2
     * => A
     */
    $substractList[] = (($list[0] + $list[1]) - $list[$nth]) / 2;

    for ($i = 0; $i < $nth; ++$i) {
        $substractList[] = ($list[$i] - $substractList[0]);
    }

//    $substractList[3] = $substractTotal - ($list[$nth - 1] + $substractList[0]);


    return $substractList;
}


$list = [5, 8, 14, 28, 40, 11, 17, 31, 43, 20, 34, 46, 40, 52, 66];

print_r(findSubstractList($list));

/**
 * P ) [6, 11, 101, 15, 105, 110];
 * S ) [1, 5, 10, 100]
 *
 * P ) [5, 8, 14, 28, 40, 11, 17, 31, 43, 20, 34, 46, 40, 52, 66];
 * S ) [1, 4, 7, 13, 27, 39]
 *
*/

my working php solution
time complexity : O( (n * (n-2)) + 3 + n) with helper variables.
space complexity : almost same with time complextiy.

function getSublistSize($length)
{
    $i = 2;
    $n = 0;

    while ($i <= $length) {
        if (is_int($length / $i)) {
            if ($length == $i * ($i + 1) / 2) {
                return ($i + 1);
            }
        }

        ++$i;
    }

    return $n;
}

function findSubstractList(array $list)
{
    $length = count($list);

    $n = getSublistSize($length);
    $nth = $n - 1;

    $substractList = [];
    $substractTotal = array_sum($list) / ($length / 2); // A + B + C + D

    /**
     * formula : A = (list[0] + list[1] - list[nth -1]) / 2
     * list[0] = A + B,
     * list[1] = A + C,
     * list[nth - 1] = B + C
     *
     * =>  ((A + B) + (A + C) - (B + C)) / 2
     * => (A + A + (B + C - B - C)) / 2
     * => (2A + 0) / 2 => 2A / 2
     * => A
     */
    $substractList[] = (($list[0] + $list[1]) - $list[$nth]) / 2;

    for ($i = 0; $i < $nth; ++$i) {
        $substractList[] = ($list[$i] - $substractList[0]);
    }

//    $substractList[3] = $substractTotal - ($list[$nth - 1] + $substractList[0]);


    return $substractList;
}


$list = [5, 8, 14, 28, 40, 11, 17, 31, 43, 20, 34, 46, 40, 52, 66];

print_r(findSubstractList($list));

/**
 * P ) [6, 11, 101, 15, 105, 110];
 * S ) [1, 5, 10, 100]
 *
 * P ) [5, 8, 14, 28, 40, 11, 17, 31, 43, 20, 34, 46, 40, 52, 66];
 * S ) [1, 4, 7, 13, 27, 39]
 *
*/

I don't think you can compute this if order in P is not specified. The order in P must be P1 = x1+x2, P2 = x1+x3, P3 = x1+x4... P_last = x(n-1) + xn.
Otherwise, each permutation of the P could give a set of xk solution.

#include <stdio.h>
#define MAX 100000

void printPairs(int arr[], int arr_size, int sum)
{
int i, temp;
bool binMap[MAX] = { 0 }; /*initialize hash map as 0*/

for (i = 0; i < arr_size; i++)
{
temp = sum - arr[i];
if (temp >= 0 && binMap[temp] == 1)
printf("Pair with given sum %d is (%d, %d) \n",
sum, arr[i], temp);
binMap[arr[i]] = 1;
}
}

/* Driver program to test above function */
int main()
{
int A[] = { x1, x2, x3, x4 };
int Sum[] = { x1 + x2, x1 + x3, x1 + x4, x2 + x3, x2 + x4, x3 + x4,};

int arr_size = 4;

for (int i = 0; i<arr_size; i++)
printPairs(A, arr_size, Sum[i]);

getchar();
return 0;
}

if it's defined order as given then we can try
1. Add given array sum= 3(x1+x2+x3+x4)
2. calculate x1+x2+x3+x4 , total = sum/3
3. There will be nc2 elements. Calculate, halfsum from n/2 to n = 2(x2+x3+x4)
4. Then calculate halftotal = halfsum/2 (x2+x3+x4)
5. x1 = now (2) - (4)
6, it's easy to get x2,x3, x4 from first half of elements

do anyone disagree?