1689. Partitioning Into Minimum Number Of Deci-Binary Numbers

Time: O(|n|)

Space: O(1)

Intuition

Minimum number of operations to reduce n to 0, where op is +1 or -1. When n is even: /2 is implicit (use binary representation). Count 1-bits + carry analysis.

Algorithm

1Count 1s in binary representation. Each isolated 1 takes 2 ops (subtract to clear). Consecutive 1s optimized with carry.
2Simulate: while n>0, if n&1: if n&2 and n>3: n++ else n--. Else n>>=1. Count ops.

Common Pitfalls

•For consecutive 1s, adding 1 turns them into a carry (fewer total operations). Greedy simulation.

1689.cs

// Approach: The answer is the maximum digit in n (each deci-binary number contributes 1 to each digit position).
// Time: O(|n|) Space: O(1)

public class Solution
{
    public int MinPartitions(string n)
    {
        return n.Max(c => c - '0');
    }
}

Was this solution helpful?