Coding questions · Akuna Capital

Compute min operations to transform integers

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 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.

Minimum Operations to Transform A into B

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:

Subtract 1 from the current value.
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.

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.