Can we use DP?
Lets follow a bottom up approach to build the sequence. Since the sequence is contiguous we can either subtract the element at the left most index to get closer to N or added the element next to rightmost element of the current subsequence or do this simultaneously.
table[left + 1][right] = table[left][right] - array[left]
table[left][right + 1] = table[left][right] + array[right]
table[left + 1][right + 1] = table[left][right] - array[left] + array[right]
Terminate the loops when the sum reaches N. Since we are not looking for a mimimum/maximum sequence I am not sure if DP is needed here.
Cheers,
Padmanabhan
On 4/9/06, Dhyanesh <[EMAIL PROTECTED]> wrote:
I dont see how this works for an array like :
2, 4, 8, 16, 32, 64
and N = 12. For this array your algo never has the condition
arr[i]%a[i]=1 as true.
-Dhyanesh
On 4/9/06, blufox <[EMAIL PROTECTED]> wrote:
>
> shishir wrote:
> > Given an array of integers and a number N, find if there exists a
> > consecutive series of numbers in this array which sum up to N.
> Algorithm:
> start
> sort array in increasing order
> sum = 0
> i = 0
> for i = 0 to i < NUM_ARR_ELEMENTS
>
> if arr[i]%a[i+1] == 1
> do
> sum += a[i]
> continue
> end if
> else
> do
> sum = 0
> continue
> end else
> end for
> if sum == N
> print "exists"
> else
> print "doesnot exists"
>
> stop
>
> Please correct me if i am wrong somewhere :)
> Thank you
> pradeep
> >
> > Regards,
> > Shishir
>
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
