Problem Statement
n birds on a tree want to learn natural numbers. They start singing all natural numbers in the increasing order starting from 1. When a number K is sung, K birds fly away from the tree. If, at any second, the number of birds on the tree is strictly less than the number which must be sung, the birds restart the game and start singing the numbers from 1 again.
You are given an
Definition
- Class:
- FunnyBirds
- Method:
- gameTime
- Parameters:
- int
- Returns:
- int
- Method signature:
- int gameTime(int n)
- (be sure your method is public)
Constraints
- n will be between 1 and 10^9, inclusive.
Examples
1
Returns: 1
There is just one bird who flies at the first second.
3
Returns: 2
One bird flies away at the first second, the other two at the next one.
4
Returns: 3
At second 1, birds sing "one" and one of four birds flies away (with 3 birds remaining on the tree). At second 2, birds sing "two" and two of three birds fly away. At the third, the birds restart the game from 1 and the last bird flies away.
14
Returns: 7
During the first four seconds the birds will count from 1 to 4, so (1 + 2 + 3 + 4) = 10 birds will fly away, with 4 birds left on the tree. The game will be restarted from 1, so 1 and 2 birds will fly away on seconds 5 and 6 respectively. On second 7, the birds will restart the game again and the only remaining bird will fly away.
100
Returns: 18
101
Returns: 17
102
Returns: 18
103
Returns: 19
100000000
Returns: 14286
100000001
Returns: 14287
100000002
Returns: 14288
100000003
Returns: 14288
100000004
Returns: 14289
100000005
Returns: 14290
999999999
Returns: 45018
1000000000
Returns: 45019
2
Returns: 2
235143265
Returns: 21862
9876543
Returns: 4539
999961560
Returns: 44720
999961559
Returns: 45039
999961561
Returns: 44721