for ( i=0 to i=N-1 ) { // This inner for-loop can be run in parallel, as there is no dependency wrt previously computed values or the values at other indices. // you are just blindly adding the value at A[i] to all the elements of the sub-array B[0 - j ] and hence can be run in parallel. for ( j = i to j = 0 ) { sum[j] = sum[j] + A[ i] product[j]= product[j] * A [i]
if ( sum[j]==sum and product[j] ==product ) Answer is A [ j to i ] } } Kishen On Wed, Oct 20, 2010 at 12:34 PM, Lily Aldrin <lily.hi...@gmail.com> wrote: > @rahul the code doesn't fail for the case you gave. Please check. > > Also Kishen can you explain how is the complexity for two loops runninf in > parallel equal to O(1). > > > On Wed, Oct 20, 2010 at 3:06 PM, rahul patil < > rahul.deshmukhpa...@gmail.com> wrote: > >> >> >> On Wed, Oct 20, 2010 at 5:11 AM, 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 ) { >>> >> >> >> why till 0? >> >> if S=107 , P= 210 >> >> and array is 10, -3 , 2 , 105, 13 >> >> code will fail >> >> >>> 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> >>>>> . >>>>> 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> >>>> . >>>> 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. >>> >> >> >> >> -- >> Regards, >> Rahul Patil >> >> -- >> 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.