Finding minimum number of days

Question

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.

Answer 1

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.