I am running my algorithm for your values -
I will just show it for sum.
Array B [ 0 0 0 0 0 ]
i = 0
Array B [ 10 0 0 0 0 ]
i = 1
Array B [7 -3 0 0 0 ]
i = 2
Array B [ 9 -1 2 0 0 ]
i=3
Array B [ 116 104 107 105 0 ]
You will stop here and the answer is the range [ k to i ] which is A [ 2 to
3 ]
I am attaching the modified algorithm.
-------------
for ( i=0 to i=N-1 )
{
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 ]
}
}
----------------------------
You can even flag the indexes whose sum or product exceeds the requirement,
so that you don't add or multiply at these indexes in the next set of
iterations, making it even more efficient algorithm.
Negative values do not affect this algorithm.
Kishen
On Wed, Oct 20, 2010 at 4:36 AM, 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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
