EasyDpAI interview only
Minimum Operations to Make N Using Add One or Double
Asked atgoogleamazonmicrosoftbloomberg
01 · Problem
You start with the value 0. In one operation you can either add 1 to the current value or double it (multiply by 2).
Given a non-negative integer n, return the minimum number of operations needed to reach exactly n. For n = 0 the answer is 0.
02 · Examples
Example 01
Input
n = 5
Output
4
0 -> 1 (add) -> 2 (double) -> 4 (double) -> 5 (add).
Example 02
Input
n = 8
Output
4
0 -> 1 (add) -> 2 (double) -> 4 (double) -> 8 (double).
Example 03
Input
n = 7
Output
5
0 -> 1 -> 2 -> 3 -> 6 -> 7 using add, double, add, double, add.
03 · Constraints
- 010 <= n <= 109
- 02You start from 0
- 03Each operation is either +1 or x2
04 · Optimal complexity
- Time
- O(log n)
- Space
- O(1)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.