1526. Minimum Number of Increments on Subarrays to Form a Target Array

Time: O(n)

Space: O(1)

Intuition

The broken calculator allows: if X > Y: X-1. If X < Y: X*2. Work backwards from Y to X: if Y is odd, Y+1. If Y is even, Y/2. Count steps.

Algorithm

1While Y > X: if Y odd, Y++; else Y /= 2. Steps++.
2Return steps + (X - Y) for remaining decrements.

Common Pitfalls

•Work backward from Y. When Y is odd, incrementing (reverse of -1 on target side) brings it to even for halving.

1526.cs

// Approach: Each position starts from the previous; only increases over the previous element require new operations.
// Time: O(n) Space: O(1)

public class Solution
{
    public int MinNumberOperations(int[] target)
    {
        // Initialize the result with the first element's value
        // This represents the initial operations needed to build the first position
        int totalOperations = target[0];

        // Iterate through the array starting from the second element
        for (int i = 1; i < target.Length; ++i)
        {
            // If current element is greater than the previous element,
            // we need additional operations equal to the difference
            if (target[i] > target[i - 1])
                totalOperations += target[i] - target[i - 1];
            // Note: If target[i] <= target[i-1], no additional operations needed
            // as we can reuse operations from building the previous element
        }

        // Return the total minimum number of operations required
        return totalOperations;
    }
}

Was this solution helpful?