@Kishen
The inner while loop increments the lower bound from where we are taking
product and sum. Total number of iterations of inner while loop can be n in
the worst case (when magnitude of last element is greater than that of given
product). So the array will be traversed twice.
Thanks,
- Ravindra
On Thu, Oct 28, 2010 at 12:38 AM, Kishen Das <kishen....@gmail.com> wrote:
> 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<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.
