Here is a simple implementation. Complexity O(n). Please let me know if you find any issues with this.
Assumptions as stated in original problem - 1- Required sub array is contiguous 2- Given array has only integers (+ve and -) // Params are array arr, length of array n, given sum and product void subarr( int* arr, int n, int sum, int prod) { int lb = 0; // Lower bound of sub array int s = 0; // Temporary sum int p = 1; // Temporary prod int mod_p = (prod > 0) ? prod : (prod * -1); // |prod| int min_p = mod_p * -1; // -|prod| int i=0; int found = 0; for(i=0; i<n; i++) { // Zero can't be sub array element if given product in not zero if((arr[i] == 0) && (prod != 0)) { lb = i+1; s = 0; p = 1; continue; } s += arr[i]; p *= arr[i]; // If product is out of range bring it back in while (p < min_p || p > mod_p) { p /= arr[lb]; s -= arr[lb]; lb++; } if( s== sum && p == prod) { printf ("Sub array is from index %d to %d\n", lb, i); found = 1; break; } } if(!found) printf("No Matching sub-array found\n"); } Thanks, - Ravindra On Mon, Oct 25, 2010 at 2:04 AM, Kishen Das <kishen....@gmail.com> wrote: > @Ravindra, Ligerdave > You guys are all right. But with GPUs, you can literally have thousands of > threads running in parallel. > Again, my aim was not to prove that my O(n ^ 2) algorithm is O ( n) on a > single processor system. > It was more towards making the members of this group to think on the lines > of Parallelism. > I long back agreed that the worst case for my algorithm is O(n^2 ) on > single processor systems. > > The current problem is a variation of original subset problem which is > NP-complete. ( http://en.wikipedia.org/wiki/Subset_sum_problem ) > > I really appreciate a O(n) solution to this problem on a single-processor > system. > > Kishen > > On Sun, Oct 24, 2010 at 1:50 PM, ravindra patel > <ravindra.it...@gmail.com>wrote: > >> >> It has nothing to do with time complexity. >> My bad. Wrong choice of words. So in the PRAM model you can say the time >> complexity is O(1), a pure theoretical concept. But the cost still remains >> O(n), isn't it. >> >> I guess now onwards we'll have to specifically ask interviewers whether >> they are asking for time complexity on scalar machine or on a parallel >> machine. Unless specified otherwise, my assumption by default would be a >> scalar one though. >> >> - Ravindra >> >> >> On Sun, Oct 24, 2010 at 11:50 PM, ravindra patel < >> ravindra.it...@gmail.com> wrote: >> >>> @ Kishen >>> So lets say you have 100 parallel processors and you are given an array >>> of 100 elements, then the loop will execute in 1 clock. Now lets say on the >>> same machine you are given a problem array of 1 million elements. So how >>> many clocks are you gonna consume, assuming all your 100 processors are >>> running in parallel. >>> >>> Buddy, with parallel processors you can reduce total computation time at >>> most by a factor of number of processors you have (which will always be a >>> constant, no matter how big it is). It has nothing to do with time >>> complexity. >>> >>> Thanks, >>> - Ravindra >>> >>> >>> On Fri, Oct 22, 2010 at 8:17 AM, Kishen Das <kishen....@gmail.com>wrote: >>> >>>> Ok, if you look at the inner loop, it is - >>>> >>>> for ( j = i to j = 0 ) { >>>> sum[j] += A[ i] >>>> product[j] *= A [ i] >>>> } >>>> >>>> This is as good as executing - >>>> sum[i] = sum [ i ] + A[ i ] ---> ( 1 ) >>>> sum[i-1]= sum[i-1]+ A[i] ----> ( 2 ) >>>> ---------- >>>> ----------- >>>> ----------- >>>> sum[0] = sum[ 0]+A[i] ------> ( i ) >>>> >>>> Each of these assignments doesn't have any dependency with other >>>> computations i.e., >>>> ( 1 ) is independent of ( 2 ) to ( i ) and so does ( 2 ) , ( 3 ) , .... >>>> ( i ) >>>> and hence each of this can be assigned to a different processor. >>>> So, each of these statements( iterations) of the inner-loop j can be run >>>> in different processors, making it O(1). >>>> >>>> I am sorry, if people are still not getting my point !!! >>>> This is the best I can do !!! >>>> >>>> Kishen >>>> >>>> On Thu, Oct 21, 2010 at 9:08 AM, ligerdave <david.c...@gmail.com>wrote: >>>> >>>>> @Kishen >>>>> >>>>> I don't have much knowledge on parallel computation in OpenCL or CUDA. >>>>> Do you mean parallelised="not have to do the computation at all"? >>>>> did you mean without knowing the boundary of the inner loop which is >>>>> depended on the outer loop, the inner loop would be smart enough to >>>>> figure out the i and j? >>>>> >>>>> On Oct 20, 7:33 pm, Kishen Das <kishen....@gmail.com> wrote: >>>>> > Well, looks like people are not understanding when I say "run a loop >>>>> in >>>>> > parallel "!!! >>>>> > >>>>> > Please look at some of the examples on Nvidia website on how >>>>> computations >>>>> > can be parallelised in OpenCL or CUDA. >>>>> > And also some of the high level programming languages like Scala >>>>> which is >>>>> > also providing these parallel constructs. >>>>> > >>>>> > If you don't understand GPUs or not familiar with parallel constructs >>>>> in >>>>> > Java, then my algorithm will definitely look like O ( n ^ 2 ). >>>>> > >>>>> > Kishen >>>>> > >>>>> > >>>>> > >>>>> > On Wed, Oct 20, 2010 at 4:25 PM, ligerdave <david.c...@gmail.com> >>>>> wrote: >>>>> > > @Kishen >>>>> > > as long as you have one for loop in another, you wont have O(n). it >>>>> > > will most likely run O(n^2) >>>>> > >>>>> > > On Oct 19, 7:41 pm, Kishen Das <kishen....@gmail.com> wrote: >>>>> > > > In the below code the jth and kth inner for loops can be run in >>>>> parallel >>>>> > > > making them O(1) and the entire thing O(n). >>>>> > >>>>> > > > for ( i=0 to i=N-1 ) >>>>> > > > { >>>>> > >>>>> > > > for ( j = i to j = 0 ) { >>>>> > > > sum[j] += A[ i] >>>>> > > > product[j] *= A [ i] >>>>> > >>>>> > > > } >>>>> > >>>>> > > > for( k=0 to k= i ) >>>>> > > > if ( sum[k] == S and product[k] == P ) { >>>>> > > > Answer is the sub array A[k to i ] >>>>> > > > break >>>>> > >>>>> > > > } >>>>> > > > } >>>>> > >>>>> > > > Kishen >>>>> > >>>>> > > > On Tue, Oct 19, 2010 at 11:36 AM, abhishek singh < >>>>> iiita2007...@gmail.com >>>>> > > >wrote: >>>>> > >>>>> > > > > @ Rahul patil ofcourse array may have negative or positive >>>>> integers >>>>> > >>>>> > > > > @ Kishen both O(n) and O(n logn) solutions was asked in this >>>>> yahoo >>>>> > > coding >>>>> > > > > round question >>>>> > >>>>> > > > > On Tue, Oct 19, 2010 at 1:28 PM, Abhishek Kumar Singh < >>>>> > > > > iiita2007...@gmail.com> wrote: >>>>> > >>>>> > > > >> Given an array of length N. How will you find the minimum >>>>> length >>>>> > > > >> contiguous sub - array of whose sum is S and whose product is >>>>> P . Here >>>>> > > > >> S and P will be given to you. >>>>> > >>>>> > > > >> -- >>>>> > > > >> You received this message because you are subscribed to the >>>>> Google >>>>> > > Groups >>>>> > > > >> "Algorithm Geeks" group. >>>>> > > > >> To post to this group, send email to >>>>> algoge...@googlegroups.com. >>>>> > > > >> To unsubscribe from this group, send email to >>>>> > > > >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>>>> <algogeeks%2bunsubscr...@googlegroups .com> >>>>> > > <algogeeks%2bunsubscr...@googlegroups .com> >>>>> > > > >> . >>>>> > > > >> For more options, visit this group at >>>>> > > > >>http://groups.google.com/group/algogeeks?hl=en. >>>>> > >>>>> > > > > -- >>>>> > > > > ABHISHEK KUMAR SINGH >>>>> > > > > BTECH (INFORMATION TECHNOLOGY) >>>>> > > > > IIIT ALLAHABAD >>>>> > > > > 9956640538 >>>>> > >>>>> > > > > -- >>>>> > > > > You received this message because you are subscribed to the >>>>> Google >>>>> > > Groups >>>>> > > > > "Algorithm Geeks" group. >>>>> > > > > To post to this group, send email to >>>>> algoge...@googlegroups.com. >>>>> > > > > To unsubscribe from this group, send email to >>>>> > > > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>>>> <algogeeks%2bunsubscr...@googlegroups .com> >>>>> > > <algogeeks%2bunsubscr...@googlegroups .com> >>>>> > > > > . >>>>> > > > > For more options, visit this group at >>>>> > > > >http://groups.google.com/group/algogeeks?hl=en. >>>>> > >>>>> > > -- >>>>> > > You received this message because you are subscribed to the Google >>>>> Groups >>>>> > > "Algorithm Geeks" group. >>>>> > > To post to this group, send email to algoge...@googlegroups.com. >>>>> > > To unsubscribe from this group, send email to >>>>> > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>>>> <algogeeks%2bunsubscr...@googlegroups .com> >>>>> > > . >>>>> > > For more options, visit this group at >>>>> > >http://groups.google.com/group/algogeeks?hl=en. >>>>> >>>>> -- >>>>> You received this message because you are subscribed to the Google >>>>> Groups "Algorithm Geeks" group. >>>>> To post to this group, send email to algoge...@googlegroups.com. >>>>> To unsubscribe from this group, send email to >>>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>>>> . >>>>> For more options, visit this group at >>>>> http://groups.google.com/group/algogeeks?hl=en. >>>>> >>>>> >>>> -- >>>> You received this message because you are subscribed to the Google >>>> Groups "Algorithm Geeks" group. >>>> To post to this group, send email to algoge...@googlegroups.com. >>>> To unsubscribe from this group, send email to >>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>>> . >>>> For more options, visit this group at >>>> http://groups.google.com/group/algogeeks?hl=en. >>>> >>> >>> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.