Compute min operations to transform integers
Company: Akuna Capital
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
Given integers A and B, transform A into B using the minimum number of operations. Allowed operations:
(
1) subtract 1 from the current value;
(
2) multiply the current value by 2. For each sample, determine the minimum number of operations and explain your approach and its time complexity: Sample 01: A = 1, B = 2; Sample 02: A = 9, B = 1; Sample 03: A = 2, B = 10; Sample 04: A = 100, B = 500.
Quick Answer: This question evaluates algorithmic problem-solving skills related to integer transformations and reasoning about sequences of allowed operations, focusing on optimizing the number of steps. It is commonly used in the Coding & Algorithms domain to assess practical application of algorithmic thinking and time-complexity analysis, testing efficiency reasoning rather than purely conceptual knowledge.
Given two integers `A` and `B`, transform `A` into `B` using the minimum number of operations. At each step you may apply exactly one of the following operations to the current value:
1. **Subtract 1** from the current value.
2. **Multiply** the current value **by 2**.
Return the minimum number of operations needed to turn `A` into `B`.
**Approach (reverse-greedy).** Searching forward from `A` is expensive because multiplying by 2 explodes the state space. Instead, work backward from `B` toward `A`, inverting each operation:
- The inverse of "multiply by 2" is "divide by 2" (only valid when the value is even).
- The inverse of "subtract 1" is "add 1".
While `B > A`: if `B` is even, halve it (undo a multiply); if `B` is odd, add 1 (undo a subtract so it becomes even and can later be halved). Each such step counts as one operation. Once `B <= A`, the only remaining way to reach `A` is to subtract 1 repeatedly, which adds exactly `A - B` more operations. This greedy is provably optimal: a smaller odd target can only be reached from a larger value via a `-1` step, so making `B` even by `+1` (reverse) before halving is always at least as good as any alternative.
**Examples:**
- `A = 1, B = 2`: `1 x 2 = 2` -> **1** operation.
- `A = 9, B = 1`: subtract 1 eight times -> **8** operations.
- `A = 2, B = 10`: `2 x 2 = 4`, `4 - 1 = 3`, `3 x 2 = 6`, `6 - 1 = 5`, `5 x 2 = 10` -> **5** operations.
- `A = 100, B = 500`: **41** operations.
Constraints
- A and B are integers.
- When B <= A, the answer is simply A - B (only subtractions are useful).
- When B > A, multiplications are required and the reverse-greedy halving applies.
- Values can be large (e.g. up to ~10^9); the O(log B) approach handles them instantly.
Examples
Input: (1, 2)
Expected Output: 1
Explanation: 1 x 2 = 2 in a single multiply operation.
Input: (9, 1)
Expected Output: 8
Explanation: B < A, so subtract 1 eight times: 9 -> 8 -> ... -> 1.
Hints
- Working forward from A is hard because multiply-by-2 branches explode. Try reasoning backward from B instead.
- Invert the operations: 'multiply by 2' becomes 'divide by 2' (only when the value is even); 'subtract 1' becomes 'add 1'.
- While B > A: if B is even, halve it; if B is odd, add 1 to make it even. Count each as one operation.
- Once B <= A, the remaining cost is exactly A - B subtractions — no multiplications can help anymore.