CareerCup

I don't think there is any better solution than O(n^2) time. Sort all elements of A and B. Now for each element in C find if u can get a sum of -C using one element each from A,B (which can be done in O(n) time since A,B are sorted now).

bool isPossible(int value,const vector<int> &A,const vector<int> &B){
        int index1=0,index2=(int)B.size()-1.
        bool flag=0;
        for(;index1<(int)A.size() && index2>=0;){
              if(sum==A[index1]+B[index2]){
                    flag = 1;
                    break;
              }
              else if(sum>A[index1]+B[index2]) index1++;
               else index2--;
        }
       return flag;
}

Run the above function for each element of C. That's it.

if there is no restriction in space complexity then easily it can be solved in n^2. it der restriction in space ?????

Just my hunch here, but if ANY of the three numbers from each list sum up to 0, couldnt you just look and see if each list contains a 0? If they do, then those 3 combined would equal 0, no?

lists may contain -ve no so it wont work...

create o(n^2) size sorted array from the lists that contain all the additions possible..

look for -c of each element from the list C ..do binary search..

o(n ln n^2)+ o(n^2)

someone double check me plz.

//The idea is to hash one of them in O(n) and then double loop through remaining 2
//in O((n^2)+C)=O(n^2). Here is a generic algorithm that finds sum to any given //target

public static void main(String[] args) {
int[] a = { 2, 4, 5, 6, 7, 8, 9, -9, 2, -5 };
int[] b = { 4, 5, 6 };
int[] c = { -6, 0, 5, 1 };

System.out.println(findSumTo(a, b, c, 0));
}

public static boolean findSumTo(int[] a, int[] b, int[] c, int target) {
// hash c
Set<Integer> myhash = new HashSet<Integer>();
for (int i = 0; i < c.length; i++) {
myhash.add(c[i]);
}
// loop through second ones in O(n^2)
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < b.length; j++) {
// check to see if c has the opposite of their sum
int val1=a[i];
int val2=b[j];
if (myhash.contains(target - (val1+val2))) {
//System.out.println("{ "+val1+", "+val2+", "+(target-(val1+val2))+"}");
return true;
}
}
}
return false;
}

It can be solved in O(N^2 LogN) with the explaination given by @aditiknath.

#include<stdio.h>
int n=5;
int a[5]={0,1,2,3,4};
int b[5]={1,2,3,3,5};
int c[5]={0,2,-5,6,9};
int findindex()
{
int flag=0;
int i=0,j=0,k=0;
while(i<n-1)
{
if((a[i]+b[j]+c[k])!=0)
{
if(j<n-1)
{
if(k<n-1)
{
//printf("%d",k) ;
k++;
}
else
{
//printf("\n jvalue %d \n",j) ;
j++;
k=0;
}
}
else
{
i++;
j=0;
k=0;
}
}
else
{
flag=1;
break;
}

}

return flag;
}
int main()
{
printf("%d",findindex());
return 0;
}

1st of all its O(n^3) solution as for each value in C u are checking each combination of A and B. 2nd of all, all 3 are linked list. 3rd of all why are you sorting list A and B when you are using all combination of A and B ??