Problem Statement
Alice has invited her two best friends, Charlie and Eric, to her birthday party. She has K boxes containing gifts for them. The boxes are numbered from 1 to K. For each i, box number i contains Fi gifts, where Fi is the ith Fibonacci number. (F1 = 1, F2 = 1, and for each i > 2, Fi = Fi - 1 + Fi - 2.)
Alice likes both of her friends equally, so she wants to distribute these K boxes between them in such a way that both of them get an equal total number of gifts.
If that is possible, return a
If there is no solution, return the
Definition
- Class:
- AlicesBirthday
- Method:
- partition
- Parameters:
- int
- Returns:
- int[]
- Method signature:
- int[] partition(int k)
- (be sure your method is public)
Notes
- The first few Fibonacci numbers are 1, 1, 2, 3, 5, 8, 13, 21, ...
Constraints
- K will be between 1 and 40, inclusive.
Examples
3
Returns: {3 }
There are K = 3 boxes containing gifts. Box 1 contains F1 = 1 gift, box 2 contains F2 = 1 gift, and box 3 contains F3 = 2 gifts. Giving boxes #1 and #2 to Charlie and box #3 to Eric means that each of them receives two gifts. The returned array represents the numbers of the boxes received by Eric in this solution. {1, 2} and {2, 1} are two other valid return values for this test case.
5
Returns: {5, 1 }
F1 + F5 = 1 + 5 = 6. F2 + F3 + F4 = 1 + 2 + 3 = 6.
1
Returns: {-1 }
Since there is only one box containing a single gift, there is no way for Charlie and Eric to have an equal number of gifts.
8
Returns: {8, 5, 1 }
23
Returns: {23, 20, 17, 14, 11, 8, 5, 1 }
35
Returns: {35, 32, 29, 26, 23, 20, 17, 14, 11, 8, 5, 1 }
40
Returns: {-1 }
17
Returns: {17, 14, 11, 8, 5, 1 }
29
Returns: {29, 26, 23, 20, 17, 14, 11, 8, 5, 1 }
33
Returns: {33, 30, 27, 24, 21, 18, 15, 12, 9, 6, 3 }
13
Returns: {-1 }
38
Returns: {38, 35, 32, 29, 26, 23, 20, 17, 14, 11, 8, 5, 1 }
6
Returns: {6, 3 }
2
Returns: {1 }
39
Returns: {39, 36, 33, 30, 27, 24, 21, 18, 15, 12, 9, 6, 3 }
18
Returns: {18, 15, 12, 9, 6, 3 }
15
Returns: {15, 12, 9, 6, 3 }
25
Returns: {-1 }