Skip to content

UVA Problem: Subsequence(1121)

October 8, 2011

Problem Statement:

Problem Explanation:

This problem is very interesting. The main concern goes to develop a O(n) algorithm , else there is no way to avoid TLE.

I am explaning this problem with sample I/O. consider
10 15
5 1 3 5 10 7 4 9 2 8.
we need to sum up >=15 using fewest number of consecutive element.

we need two iterator first and last.
s=15;
sum=0;
first=0;
last=0;
while(1)
{
while(sum<s)
{
add A[last] to sum and increament last;
}

we get >=s using 5 element {5,1,3,5,10}.
Now,
while (sum>=s)
   {
subtract A[first] to sum and increament first;
}

diff=(last-1)- (first-1) + 1;
if(diff< minSeq)
{
minSeq=diff;
}
}

Advertisements
No comments yet

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: