Show problems as
Classic problem #231EasyMathBit ManipulationRecursion

Power of Two

Real-world version: Tally in the Doubling Run
Tracked in this browser only
Read Power of Two on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A press opens a run with one sheet in the stack and doubles the stack on every pass after that, so the stack sizes the run produces are 1, 2, 4, 8, 16 and onwards without limit.

You are handed tally, a single line lifted from the shop ledger. A ledger line may be zero, and it may be negative, because a reversal is written as a negative count.

Return true when some pass of the doubling run leaves exactly tally sheets in the stack, and false otherwise.

Examples

Example 1

Input
tally = 64
Output
true

Doubling from a single sheet gives stacks of 1, 2, 4, 8, 16, 32 and then 64, so the seventh pass of the run leaves exactly this many sheets.

Example 2

Input
tally = 6
Output
false

The run leaves 4 sheets on one pass and 8 on the next, so it never leaves 6.

Example 3

Input
tally = -64
Output
false

Every stack the run produces holds at least one sheet, so a negative ledger line is not one of them.

Constraints

  • -2^31 <= tally <= 2^31 - 1

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def in_doubling_run(tally: int) -> bool:
Java
public boolean inDoublingRun(int tally)

More on the same topics