Ugly Number
Real-world version: Reachable Batch SizeThe statement here is our own: the same inputs, outputs and technique.
A crating line assembles an order by starting from one single unit and then applying a sequence of doublers, triplers and quintuplers: each device in the line multiplies the running count by 2, by 3 or by 5. Devices may be used in any order and any number of times, and the line may also be left empty.
A count n is reachable when some arrangement of those devices produces exactly n units. The count 1 is reachable, since the empty line already delivers one unit.
Given an integer n, return true when n is reachable and false when it is not. The line never produces zero or a negative count, so any n that is not strictly positive is unreachable.
Examples
Example 1
- Input
- n = 4050
- Output
- true
One doubler, four triplers and two quintuplers turn the single starting unit into 2 * 81 * 25 = 4050 units, so the count is reachable.
Example 2
- Input
- n = 385
- Output
- false
385 units would need a device that multiplies by 7 and another that multiplies by 11, and the line has neither.
Example 3
- Input
- n = -720
- Output
- false
The line only ever reports positive counts, so a negative target cannot be produced.
Constraints
- -2^31 <= n <= 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.
def is_ugly(n: int) -> bool:public boolean isUgly(int n)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 14 test cases: 14 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's