0434EasyMathRecursion

Proving Cabinet Batch Sizes

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A sourdough bakery opens with a single loaf in the proving cabinet on its first day, and every day after that it trebles what the cabinet held the day before: one loaf, then three, then nine, then twenty-seven, and onward with no ceiling.

A stocktaker hands you one figure n copied out of the order book by hand. Return true when n is exactly the number of loaves the cabinet held on some day, and false otherwise.

Because the figure is copied by hand it may arrive as zero or as a negative number. The cabinet was never empty and never held a negative number of loaves, so such a figure is not a batch size.

Examples

Example 1

Input: n = 81
Output: true

The cabinet held eighty-one loaves four days after the first, so the figure matches a day's contents.

Example 2

Input: n = 6
Output: false

Six sits between the batches of three and nine, so no day's cabinet held exactly six loaves.

Example 3

Input: n = 243
Output: true

Two hundred and forty-three is what the cabinet held five days after the first.

Example 4

Input: n = -9
Output: false

The figure is negative, and the cabinet never held a negative number of loaves, whatever its magnitude looks like.

Constraints

-2^31 <= n <= 2^31 - 1

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def is_power_of_three(n: int) -> bool:

Java

public boolean isPowerOfThree(int n)

The intended approach

Time O(log n): the figure is divided by three until it stops dividing evenly.Space O(1): one running figure.

Reject anything below one straight away, since no day's cabinet held fewer than one loaf. Then divide the figure by three for as long as it divides evenly. What is left is the figure with all its factors of three removed, so the figure is a batch size exactly when that leftover is one. Each division shrinks the figure threefold, so the loop turns over at most twenty times for any 32-bit figure.

Pythonentry point: is_power_of_three

def is_power_of_three(n):
    # Every batch size is a bare 1 wearing some number of factors of three, so
    # strip factors of three off the figure and check that a lone 1 remains. A
    # figure below 1 is rejected before the loop starts, which is also what keeps
    # the loop finite. O(log n) time, O(1) space.
    if n < 1:
        return False
    while n % 3 == 0:
        n //= 3
    return n == 1

The obvious version

Build the whole list of batch sizes from one upward by repeated trebling, stopping once the values pass the largest 32-bit figure, then look the given figure up in that list.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_is_power_of_three(n):
    sizes = []
    value = 1
    while value <= 2147483647:
        sizes.append(value)
        value *= 3
    return n in sizes

How this problem was checked

Reference solution executed against 18 test cases — 18 passed
4 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in