# UVA Problem: 136(Steps)

October 5, 2011

**Problem Explanation:**

There exist a direct formula but I prefer this algorithm since there is no floating point calculation present here and its faster.

Here goes my algorithm

```
First find what is the maximum sum that can be made usingn element-
if n=1 -> 1 sum=1;
if n=2 -> 1,1 sum=2;
if n=3 -> 1,2,1 sum=4;
if n=4 -> 1,2,2,1 sum=6;
if n=5 -> 1,2,3,2,1 sum=9;
if n=6 -> 1,2,3,3,2,1 sum=12;
...............................
..................................
if n=100000 -> ....................
Declare an Array , A[i] and populate it with the above calculation like A[1]=1, A[2]=2, A[3]=4, A[4]=6
and so on. Now consider the input.
Suppose you are given- 45 50 calculate the difference that is 5. Using 3 element you can't make 5,
at most 4 can be made, but using 4 element you can make 6 , so its certainly possible to make 5,
Like 1 2 1 1. So the result is 4.
So you only need a binary search to find out the minimum index i in A[] that is A[i]>= difference.
And thats all. n=100000 is enough to hold the 31 bit number.
```**Hope Its understandable.**

Advertisements

No comments yet