CODEWITHSUNDEEP
algorithm
Angersmash
Angersmash

Reputation: 257

Finding minimum number of days

I got this question as a part of the interview and I am still unable to solve it. It goes like this 

    A person has to complete N units of work; the nature of work is the same. 
In order to get the hang of the work, he completes only one unit of work in the first day. 
He wishes to celebrate the completion of work, so he decides to complete one unit of work in the last day. 
Given that he is only allowed to complete x, x+1 or x-1 units of work in a day, where x is the units of work 
completed on the previous day.
How many minimum days will he take to complete N units of work?

Sample Input:
6
-1
0
2
3
9
13

Here, line 1 represents the number of input test cases.

Sample Output:
0
0
2
3
5
7

Each number represents the minimum days required for each input in the sample input.

I tried doing it using the coin change approach but was not able to do so.

Upvotes: 3

Views: 2460

Answers (3)

mIllIbyte
mIllIbyte

Reputation: 101

If you need to do exactly N units, not more, then you could use dynamic programming on the matrix a[x][y] where x is the amount of work done in the last day, y is the total amount of work, and a[x][y] is the the minimum number of days needed. You could use Dijkstra's algorithm to minimize a[1][N]. Begin with a[1][1]=1.

Upvotes: 0

Johannes Geidel
Johannes Geidel

Reputation: 126

AS you want to have the minimum amounts of days you can just say yeah x+1, since if you want the minimum amount of days, BUT you have to consider that his last day x should be 1 so you have to break at a given point and go x-1, so now we have to determine the Breakpoint.
The Breakpoint is located in the middle of the days, since you start at 1 and want to end at 1.
For example you have to do 16 units so you distribute your days like:
Work done:
1234321. 7 days worked.
When you can't make an even Breakpoint like above repeat some values 5 = 1211
Samples:

2: 11
3: 111
9: 12321
13: 1234321

Upvotes: 0

Paul Hankin
Paul Hankin

Reputation: 58281

In 2k days, it's possible to do at most 2T(k) work (where T(k) is the k'th triangular number). In 2k+1 days, it's possible to do at most T(k+1)+T(k) at most work. That's because if there's an even (2k) number of days, the most work is 1+2+3+...+k + k+(k-1)+...3+2+1. Similarly, if there's an odd (2k+1) number of days, the most work is 1+2+3+...+k+(k+1)+k+...+3+2+1.

Given this pattern, it's possible to reduce the amount of work to any value (greater than 1) -- simply reduce the work done on the day with the most work, never picking the start or end day. This never invalidates the rule that the amount of work on one day is never more than 1 difference from an adjacent day.

Call this function F. That is:

F(2k)   = 2T(k)
F(2k+1) = T(k)+T(k+1)

Recall that T(k) = k(k+1)/2, so the equations simplify:

F(2k)   = k(k+1)
F(2k+1) = k(k+1)/2 + (k+1)(k+2)/2 = (k+1)^2

Armed with these observations, you can solve the original problem by finding the smallest number of days where it's possible to do at least N units of work. That is, the smallest d such that F(d) >= N.

You can, for example, use binary search to find d, or an optimal approach is to solve the equations. The minimal even solution has d/2 * (d/2 + 1) >= N which you can solve as a quadratic equation, and the minimal odd solution has (d+1)^2/4 >= N, which has a solution d = ceil(2sqrt(N)-1). Once you've found the minimal even and odd solutions, then you can pick the smaller of the two.

Upvotes: 3

Related Questions