Problem Statement
An accurate scale is one of the most important tools of the apothecary (an old-time pharmacist). To measure the weight of an object, the apothecary places the object on one pan of the scale, along with some weights of known size, and adds more weights of known size to the other pan until the scales balance. For example, if an object weighs 17 grains, the apothecary could balance the scales by placing a 1-grain weight and a 9-grain weight in the pan with the object, and a 27-grain weight in the other pan.
The apothecary owns weights in a range of sizes starting at 1 grain. In particular, he owns one weight for each
power of 3: 1 grain, 3 grains, 9 grains, 27 grains, etc. Determine, for an object weighing W grains, how to distribute the weights among the
pans to balance the object. This distribution will be unique. Return a
Definition
- Class:
- Apothecary
- Method:
- balance
- Parameters:
- int
- Returns:
- int[]
- Method signature:
- int[] balance(int W)
- (be sure your method is public)
Constraints
- W is between 1 and 1000000, inclusive.
Examples
17
Returns: { -9, -1, 27 }
The example above.
1
Returns: { 1 }
A 1-grain weight is placed in the pan opposite the object being measured.
2016
Returns: { -243, -9, 81, 2187 }
A 9-grain weight and a 243-grain weight are placed in the pan with the object, and an 81-grain weight and a 2187-grain weight are placed in the opposite pan.
1000000
Returns: { -531441, -59049, -6561, -243, -27, 1, 81, 729, 2187, 1594323 }
2
Returns: { -1, 3 }
3
Returns: { 3 }
4
Returns: { 1, 3 }
5
Returns: { -3, -1, 9 }
6
Returns: { -3, 9 }
7
Returns: { -3, 1, 9 }
8
Returns: { -1, 9 }
9
Returns: { 9 }
14
Returns: { -9, -3, -1, 27 }
22
Returns: { -9, 1, 3, 27 }
45
Returns: { -27, -9, 81 }
84
Returns: { 3, 81 }
156
Returns: { -81, -9, 3, 243 }
316
Returns: { -9, 1, 81, 243 }
500
Returns: { -243, -9, -3, -1, 27, 729 }
911
Returns: { -81, -9, -1, 3, 27, 243, 729 }
2045
Returns: { -243, -9, -1, 3, 27, 81, 2187 }
4987
Returns: { -2187, -81, -27, -9, 1, 729, 6561 }
21345
Returns: { -729, -27, -9, -3, 243, 2187, 19683 }
69100
Returns: { -6561, -2187, -729, -243, -3, 1, 9, 81, 19683, 59049 }
101010
Returns: { -59049, -19683, -243, -81, 3, 729, 2187, 177147 }
278982
Returns: { -177147, -59049, -19683, -2187, -729, -243, -9, 27, 6561, 531441 }
402349
Returns: { -177147, -19683, -81, -9, 1, 3, 27, 2187, 6561, 59049, 531441 }
654321
Returns: { -59049, -2187, -243, -81, 3, 729, 6561, 177147, 531441 }
789123
Returns: { -729, -9, 3, 27, 81, 243, 2187, 19683, 59049, 177147, 531441 }
999999
Returns: { -531441, -59049, -6561, -243, -27, 81, 729, 2187, 1594323 }
531441
Returns: { 531441 }
803158
Returns: { -531441, -177147, -59049, -19683, -6561, -243, -27, -9, -3, 1, 81, 729, 2187, 1594323 }
797189
Returns: { -531441, -177147, -59049, -19683, -6561, -2187, -729, -243, -81, -9, -3, -1, 1594323 }
94
Returns: { 1, 3, 9, 81 }
87629
Returns: { -81, -9, -3, -1, 243, 2187, 6561, 19683, 59049 }
931112
Returns: { -531441, -177147, -19683, -729, -81, -9, -1, 27, 243, 6561, 59049, 1594323 }
723243
Returns: { -6561, -729, -9, 3, 81, 2187, 19683, 177147, 531441 }
2016
Returns: { -243, -9, 81, 2187 }
4
Returns: { 1, 3 }
1000000
Returns: { -531441, -59049, -6561, -243, -27, 1, 81, 729, 2187, 1594323 }
12
Returns: { 3, 9 }