Google Foobar Problem - Peculiar Balance

readme.txt

Peculiar balance
================

Can we save them? Beta Rabbit is trying to break into a lab that contains the only known zombie cure - but there's an obstacle. The door will only open if a challenge is solved correctly. The future of the zombified rabbit population is at stake, so Beta reads the challenge: There is a scale with an object on the left-hand side, whose mass is given in some number of units. Predictably, the task is to balance the two sides. But there is a catch: You only have this peculiar weight set, having masses 1, 3, 9, 27, ... units. That is, one for each power of 3. Being a brilliant mathematician, Beta Rabbit quickly discovers that any number of units of mass can be balanced exactly using this set.

To help Beta get into the room, write a method called answer(x), which outputs a list of strings representing where the weights should be placed, in order for the two sides to be balanced, assuming that weight on the left has mass x units.

The first element of the output list should correspond to the 1-unit weight, the second element to the 3-unit weight, and so on. Each string is one of:

"L" : put weight on left-hand side
"R" : put weight on right-hand side
"-" : do not use weight

To ensure that the output is the smallest possible, the last element of the list must not be "-".

x will always be a positive integer, no larger than 1000000000.

Languages
=========

To provide a Python solution, edit solution.py
To provide a Java solution, edit solution.java

Test cases
==========

Inputs:
    (int) x = 2
Output:
    (string list) ["L", "R"]

Inputs:
    (int) x = 8
Output:
    (string list) ["L", "-", "R"]

Use verify [file] to test your solution and see how it does. When you are finished editing your code, use submit [file] to submit your answer. If your solution passes the test cases, it will be removed from your home folder.

First Step

The Peculiar Balance is a device which contains a weight, of value n units, and gives you an infinite set of fixed weights
with values 1, 3, 9, 27, ... and so forth, all powers of three.

The known weight n is on the left side of the balance, and there is a right side (initially empty).

Your goal is to balance the Peculiar Balance, with a weight that you know (n), using only the fixed weights,
placed either on the right or the left side.

As a first step, given n, come up with a formula for M, the smallest fixed weight which, when placed on the
right-hand side, would tip the balance to the right (i.e. the smallest fixed weight that is still greater than n).

Examples:
for n = 2, M = 3, since 1 is smaller than 2, and 9 is greater than 2 but not the smallest such fixed weight
for n = 8, M = 9
for n = 10, M = 27

M should be an expression in terms of n.
You can use the functions
log3(x), which means the logarithm base 3 of x, or the power you would raise 3 to equal x.
  log3(3) = 1, log3(9) = 2, log3(27) = 3, ... it could also be a floating point number
floor(x), which means the greatest number less than or equal to x
and ceil(x) which means the smallest number greater than or equal to x,
and all other arithmetic operators or mathematical functions that you know of.
M(n) = ???