CareerCup

<pre lang="" line="1" title="CodeMonkey87639" class="run-this">#define equal()\
one = cone;\
two = ctwo;\
three = cthree;\
four = cfour;

int findFourSubNum(int *arr,int nLength, int& one, int &two, int &three, int &four, int sum)
{
int cn = arr[one]+arr[two]+arr[three]+arr[four];
if (sum == cn)
return 0;

int cone = one;
int ctwo = two;
int cthree = three;
int cfour = four;
if (cn > sum)
{
cfour--;
if (cfour == cthree)
{
cfour = cthree;
cthree--;
if (cthree <= ctwo)
return -1;
}
if (0 == findFourSubNum(arr,nLength,cone,ctwo,cthree,cfour,sum))
{
equal();
return 0;
}

cthree--;
if (cthree <= ctwo)
return -1;
if (0 == findFourSubNum(arr,nLength,cone,ctwo,cthree,cfour,sum))
{
equal();
return 0;
}
return -1;
}
else
{
cone++;
if (cone == ctwo)
{
cone = ctwo;
ctwo++;
if (ctwo >= cthree)
return -1;
}
if (0 == findFourSubNum(arr,nLength,cone,ctwo,cthree,cfour,sum))
{
equal();
return 0;
}

ctwo++;
if (ctwo >= cthree)
return -1;
if (0 == findFourSubNum(arr,nLength,cone,ctwo,cthree,cfour,sum))
{
equal();
return 0;
}
return -1;
}
}

int getFourSubNum(int *arr, int nLength, int sum)
{
if (NULL == arr)
return 0;

quickSort(arr,0,nLength-1);
int one = 0,two = 1,three = nLength-2,four = nLength-1;
int re = findFourSubNum(arr,nLength,one,two,three,four,sum);
if (0 == re)
{
printf("%d+%d+%d+%d = %d\n",arr[one],arr[two],arr[three],arr[four],sum);
}
return 0;
}
</pre><pre title="CodeMonkey87639" input="yes">
</pre>

My soln i think is similar to the prev one. though subtly different.

have 4 pointers to array at post
p1 =1,
p2 =2,
p3 = max-1,
p4 = max.

note that p1<p2<p3<p4 should always be maintained.

currSum is the current sum of the values pointed by the 4 pointers.

reqSum is the required sum which is constant

*if currSum > reqSum, then we need to decrement the sum by as little as possible, i.e. we decrement the 3rd pointer p3.
note that p3 should always > p2.
*suppose p3 becomes adjacent to p2, and the Cursum is still greateer than the reqSum, then we decrement p4

similarly if currSum < reqSum, we need to increase the sum by as little as possible so we increment p2. until p2 becomes adjacent to p3.
*suppose p2 becomes adjacent to p3, and currSum < reqSum, then increment p1.

for this problem, currently i cannot think of any proper strategy about moving which pointer at each step.
just give out my solution which is other than O(n^3), it is O(n*sum), so whether it is better or worse depends on sum...

sort(a,a+n);
for (int i=2;i<=sum/2;i++) {
    n1=i;n2=sum-i;
    // check whether there are two items in array which sums to n1, mark all of them   O(n)
    // check whether there are two items in array which sums to n2, and not conflict with above mark   O(n)
}

an alternative way to solve this problem is using dp method, something like knapsack problem. the time complexity is also O(n*sum)

O(n^2 logn) seems to be possible.
- Take pairwise sums => O(n^2)
- Sort the sums => O(n^2 logn)
- For each pair p, search for the conjugate q, such that p+q = given number
needs special checking so that p or q doesn't share any component. => O(n^2 logn) if binary search

I think this is probably lowest possible worst-case complexity to achieve. Any idea to improve the complexity?

@Supersonglj
while( (currSum > reqSum) && (p3>p2) )
{
--p3;// do --p4 only if( (p2+1 == p3) && (currSum > reqSum))
}

why i think p3 should be decremented and not p4 is because:
the array is sorted initially, lets consider following array:

[.... 7,8,9]
currently if p4 points to 9 and
p3 points to 8;
the next biggest sum which is lesser than 8+9 would have to be 7+9 and never 7+8.
since 7 is definitely going to be considered next, we have to decide which number to remove either 8 or 9. since removal of a smaller numnber(in this case 8) would give us a number closer to the previous biggest sum, we choose to decreemtn p3 and not p4.

I have one more solution..
Assumption
1. array has all diff elements.
2. array had all element's greater then 0

suppose we have number Y as a sum amount.
I will select all element's less then Y-6. suppose size is m and array A1
create another having the sum of two different element of array A1 and size mC2.suppose A2
take a element in A2 and searched for Y-element, if its there we have elements with the sum. search the element back from array A.

We already know how to find two numbers in an array than sum to a given number in O(n) time or O(n log n) time by using a hash table or sorting. Given n elements we have n ^ 2 ways of picking 2 elements from them. Lets form a new array with all possible pairs. Picking 2 elements from the new array is equivalent of picking 4 elements from the original array with n elements. In the newly formed array with n ^ 2 elements we can find 2 elements that sum to the given number O(n ^ 2) time.

<pre lang="" line="1" title="CodeMonkey94698" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
import java.math.*;
import java.util.*;
class FindFour {
static int n = 2000;
static int X = 17;
static int count4 = 0;
static int count3 = 0;
static int count1 = 0;
public int[] find4(int arr[], int target) {
int ret[] = new int[4];;
for (int i1 = 0; i1 < arr.length; i1++) for (int i2 = i1 + 1; i2 < arr.length; i2++)
for (int i3 = i2 + 1; i3 < arr.length; i3++) for (int i4 = i3 + 1; i4 < arr.length; i4++) {
count4++;
if (arr[i1] + arr[i2] + arr[i3] + arr[i4] == target) {
ret = new int[]{arr[i1], arr[i2], arr[i3], arr[i4]};

return ret;
}
}
return ret;
}

public int[] find3(int arr[], int target) {
HashSet<Integer> set = new HashSet<Integer>();
for (int i : arr) { count3++; set.add(i);}
int ret[] = new int[4];
for (int i1 = 0; i1 < arr.length; i1++) for (int i2 = i1 + 1; i2 < arr.length; i2++)
for (int i3 = i2 + 1; i3 < arr.length; i3++) {
count3++;
int v = target - arr[i1] - arr[i2] - arr[i3];
if (set.contains(v)) {
ret = new int[]{arr[i1], arr[i2], arr[i3], v };

return ret;
}
}
return ret;
}
static class Pair {
int idx1;
int idx2;

public Pair(int idx1, int idx2) {
this.idx1 = idx1;
this.idx2 = idx2;

}
boolean match(Pair p) {
return this.idx1 != p.idx1 && this.idx2 != p.idx1 && this.idx1 != p.idx2 && this.idx2 != p.idx2;
}
}
public int[] find1(int arr[], int target) {
int ret[] = new int[4];
HashMap<Integer, ArrayList> map = new HashMap<Integer, ArrayList>();
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
int v = arr[i] + arr[j];
count1++;
ArrayList<Pair> list = (ArrayList<Pair>) map.get(v);
if (list == null) {
list = new ArrayList<Pair>();
map.put(v, list);
}
list.add(new Pair(i, j));
}
}
Iterator<Integer> it = map.keySet().iterator();

while (it.hasNext()) {
Integer v = it.next();
ArrayList<Pair> list1 = (ArrayList<Pair>)map.get(v);
ArrayList<Pair> list2 = (ArrayList<Pair>)map.get(target - v);

if (list2 != null) {
Iterator<Pair> lIt1 = list1.iterator();

while (lIt1.hasNext()) {
Pair p1 = lIt1.next();

Iterator<Pair> lIt2 = list2.iterator();
while (lIt2.hasNext()) {
count1++;
Pair p2 = lIt2.next();
if (p1.match(p2)) {
return new int[]{p1.idx1, p1.idx2, p2.idx1, p2.idx2};
}
}
}
}
}

return ret;
}
public static void main(String args[]) {
long start = System.currentTimeMillis();
show("find1", new FindFour().find1(getIntArr(), X), start);
start = System.currentTimeMillis();
show("find3", new FindFour().find3(getIntArr(), X), start);
start = System.currentTimeMillis();
show("find4", new FindFour().find4(getIntArr(), X), start);

System.out.println(count1 + " " + count3 + " " + count4);
}
static void show(String title, int arr[], long start) {
long end = System.currentTimeMillis();
System.out.println("*********** " + title + " ************");
System.out.println("Time : " + (end - start) + " ms");

for (int i : arr) System.out.println(i);

}
static int[] getIntArr() {
int [] arr = new int[n];
Random r = new Random();
for (int i = 0; i < arr.length; i++) {
arr[i] = r.nextInt() % X;
}
return arr;

}
}</pre><pre title="CodeMonkey94698" input="yes">
</pre>

funny thing is that N^4 brute force is the fastest way, while N^3 is ok, but still need to build map, while the N^2 solution just took too much memory, I have reduce the test record from 200000 to 2000 to avoid out of memory. For the above code, if you just run find3 and find4, you could change n to 200000 or even bigger.

So this seems anti-algorithm. Any expert could explain?

Thanks.

Check this one out (Time complexity O(N^2))
"stackoverflow.com/questions/3569504/find-four-elements-in-array-whose-sum-equal-to-a-given-number-x"

I wrote this in ruby, works well if the array contains contiguous values, it should be pretty close to linear.

If the array does NOT contain contiguous values (gaps) I'd traverse the array once to create the list of all possible sums, putting each sum into a hash key=sum, value= "array indices". Than you could query on the hash. I'm not saying that's great. Thoughts?


#! /usr/bin/ruby

@arr = (1..50000).to_a
@max = @arr[@arr.length-1] + @arr[@arr.length-2] + @arr[@arr.length-3] + @arr[@arr.length-4]
@min = 1+2+3+4
puts "Please enter an integer number less than #{@max} and I will tell you 4 numbers that can add up to it"
final_value = gets.chomp.to_i

@value1 = 0
@value2 = 1
@value3 = 2
@value4 = 3

def sum()
@arr[@value1]+@arr[@value2]+@arr[@value3]+@arr[@value4]
end

def move_posts_right()
if @value4 < @arr.length - 1
@value4 += 1
elsif @value3 < @value4 - 1
@value3 += 1
elsif @value2 < @value3 - 1
@value2 += 1
elsif @value1 < @value2 - 1
@value1 += 1
else
raise 'not possible final value to large'
end
end

def move_posts_left()
if @value1 > 0
@value1 -= 1
elsif @value2 > @value1 + 1
@value2 -= 1
elsif @value3 > @value2 + 1
@value3 -= 1
elsif @value4 > @value3 + 1
@value4 -= 1
else
raise 'not possible final value to small'
end
end

current_value = sum

while current_value != final_value do
if (current_value < final_value)
move_posts_right
else
move_posts_left
end
current_value = sum
end

puts "4 numbers that add upto #{final_value} are #{@arr[@value1]}, #{@arr[@value2]}, #{@arr[@value3]}, #{@arr[@value4]}"

Here i am putting two pointers at first and last index and take their sum(say x) keep them fixed and then find pair with sum(sum=given_sum-x) using two pointer method.now after one round move these fixed pointers inside and do the same .. hope i am clear... complexity O(N^2)

int main()
{
int arr[]={2,3,4,5,6,7,8,9,12,15};
int i=0;
int j=9;
int k=1;
int l=8;
int num=30;
int find=0;
while(i<j)
{
find=num-(arr[i]+arr[j]);

while(k<l)
{
if((arr[k]+arr[l])==find)
{ cout << arr[i] << "---" << arr[j] <<"---" << arr[k] <<"--" << arr[l] << endl;
k++;l--;
}
else if((arr[k]+arr[l])>find)
l--;
else
k++;
}
i++;j--;
k=1;
l=8;
}
getch();
return 1;
}

#include <stdio.h>

int sum(int ar[], int n, int req_sum)
{
	int a, b, c, d, sum;
	a = 0;
	b = 1;
	c = n-2;
	d = n-1;

	while(b<c)
	{
		sum = ar[a] + ar[b] + ar[c] + ar[d];

		if (sum == req_sum)
		{
			printf("%d: %d: %d: %d:", ar[a], ar[b], ar[c], ar[d]);
			return 0;
		}
		else if(sum < req_sum)
		{
			b++;
			if(b>=c)
			{
				if(a == b-1)
					return -1;
				else
				{
					a++;
					b = a+1;
				}

			}

		}
		else
		{
			c--;
			if(c <= b)
			{
				if(c == d-1)
					return -1;
				else
				{
					d--;
					c = d-1;
				}

			}

		}

	}

}


int main()
{
	int n, a[20], req_sum, i;

	printf("enter num elements:\n");
	scanf("%d", &n);
	printf("enter req sum:\n");
	scanf("%d", &req_sum);
	printf("enter array:\n");
	
	for(i=0; i<n; i++)
	scanf("%d", &a[i]);

	sum(a, n, req_sum);
	getchar();
	getchar();
}

1)Sort the array a[] by O(nlogn); if a[0]+a[1]+a[2]+a[3] > sum or a[n-1]+a[n-2]+a[n-3]+a[n-4] < sum, return null;
2)Assign four indexes as a1=n-1, a2=n-2, a3=n-3, a4=n-4; while a1!=0 or a2!=1 or a3!=2 or a4!=3, do following:
3)if a1-1>0, deduction[0] = a[a1]-a[a1-1]; else temp[0] = MAX;
4)if a2-1>a1, deduction[1] = a[a2]-a[a2-1]; else temp[1] = MAX;
5)if a3-1>a2, deduction[2] = a[a3]-a[a3-1]; else temp[2] = MAX;
6)if a4-1>a3, deduction[3] = a[a4]-a[a4-1]; else temp[3] = MAX;
7)pick from a1, a2, a3, a4 which is min(deduction), let it minus 1;
8)if a[a1]+a[a2]+a[a3]+a[a4] == sum, break;
9)if a[a1]+a[a2]+a[a3]+a[a4] < sum, return null; end while loop;
10)return null;

a + b + c + d = sum;
=> a + b = sum - (c + d)

(1) Find all possible sums of (a + b). O(n^2)
(2) Let that be stored in array of structure A along with values of a, b.
(3) Let sum - (c + d) be stored in B and also the corresponding values of c, d be stored along with it in a data structure.
(4) Sort A, B.
(5) For each element in A , do a binary search in B and if found then check if the elements are same. If not then do a count++.

solution keeping track of duplicates as well. if array is 11111111 then 8*7*6*5 subsets are possible

Q(lo, lm, um, hi)
	if(lo>lm>um>hi) // any of the condition meets
		return
	cs = a[lo] + a[lm] + a[um] + a[hi]
	if(cs == k)
		Q(lo, lm, um-1, hi)
		Q(lo, lm, um-1, hi-1)
		Q(lo, lm+1, um, hi)
		Q(lo+1, lm+1, um, hi)
		c++
	else if(cs < k)
		Q(lo, lm+1, um, hi)
		Q(lo+1, lm+1, um, hi)
	else if(cs > k)
		Q(lo, lm, um-1, hi)
		Q(lo, lm, um-1, hi-1)

main()
        QS() //quick sort..
	Q(0, 1, n-2, n-1)