Reduce a Number to 1

Problem Statement

Given a positive integer n, reduce it to 1 using the following operations:

• If n is even, divide it by 2 → n = n / 2
• If n is odd, you can either subtract 1 or add 1 → n = n - 1 or n = n + 1

Return the minimum number of operations required to reduce n to 1.

Constraints:

• 1 ≤ n ≤ 2^31 - 1

Allowed Operations:

• If even: n = n / 2
• If odd: n = n - 1orn = n + 1

Examples

Example 1:

Input: n = 8
Output: 3

Explanation: 8 -> 4 -> 2 -> 1

Example 2:

Input: n = 7
Output: 4

Explanation: 7 -> 8 -> 4 -> 2 -> 1
(or 7 -> 6 -> 3 -> 2 -> 1 -- also 4 steps, both valid)

Example 3:

Input: n = 15
Output: 5

Explanation: 15 -> 16 -> 8 -> 4 -> 2 -> 1

Different Approaches

1️⃣