Follow

# Go4Fun - Functional programming and more

Follow # Rust Interview Puzzles: Ugly numbers

go4fun.fun
·Jan 23, 2023·

### Problem

Given a provided integer number `n`, we need to check whether this number is Ugly. Ugly numbers are a sequence of numbers whose only prime factors are `2`, `3` or `5`. In other words, these numbers are divisible only by `2`, `3` or `5` prime numbers (but not by other prime numbers). The first few ugly numbers are `1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18..`. By convention, `1` is also included.

#### Examples:

 Input `n` Output Explanation `10` `true` Prime factors: `2, 5` `11` `false` Prime factors: `11` `12` `true` Prime factors: `2, 3` `13` `false` Prime factors: `13` `14` `false` Prime factors: `2, 7` `15` `true` Prime factors: `3, 5`

### Solution

``````fn is_ugly_number(mut n: i32) -> bool {
while n > 1 {
match n {
_ if n % 2 == 0 => n /= 2,
_ if n % 3 == 0 => n /= 3,
_ if n % 5 == 0 => n /= 5,
_ => return false,
}
}
return n == 1;
}
``````

### Explanation

One simple way to solve the puzzle is to iteratively divide the input number `n` by `2` as long as it is divisible (`n % 2 == 0`). If the current number `n` is not divisible by `2`, then we try to divide it by `3` and `5`. If the current number `n` that is not divisible by any of `2, 3, 5`, then we could conclude that the number is not ugly (`return false`). Otherwise, we continue `while n > 1`. In the end, the remaining number `n` should be equal to `1` for the input number to be deemed Ugly.

### Complexity

The time complexity of the solution is `O(log n)` (where `n` is the input integer number). The auxiliary space complexity is `O(1)`.

Rust Playground with this code