How do you claim that its O(n) when you have a while-loop inside the
for-loop?
What is the complexity of the inner while loop ?
What is the worst case complexity, if only the last element of the array
matches the product and the sum?
Kishen
On Wed, Oct 27, 2010 at 2:01 PM, ravindra patel <ravindra.it...@gmail.com>wrote:
> 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<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.
