Sum of Sortable Integers - Solution & Explanation

Problem Overview: You are given a collection of integers and must identify which ones are sortable. An integer is considered sortable if its digits can be rearranged so the resulting number has digits in non‑decreasing order. The task is to compute the sum of all integers that satisfy this condition.

Approach 1: Brute Force Digit Permutations (O(n * d!))

The most direct idea is to generate every permutation of the digits of each number and check if any permutation forms a non‑decreasing sequence. Convert the number to a string, generate permutations, and validate whether digits increase or stay equal as you scan from left to right. The first valid permutation marks the integer as sortable. This approach quickly becomes impractical because the number of permutations grows factorially with the digit count (d!). Space complexity is O(d!) due to storing permutations during generation.

Approach 2: Greedy Digit Sorting (O(n * d log d))

A much simpler observation: if digits can be rearranged to become non‑decreasing, sorting the digits directly gives that arrangement. Convert the integer to a digit array, sort it, and verify the resulting sequence is valid under the problem constraints. Since sorting produces the lexicographically smallest ordering, the check becomes trivial. Each integer requires sorting d digits, giving O(d log d) time and O(d) extra space. This approach relies on basic sorting operations and works well for moderate digit counts.

Approach 3: Digit Frequency Counting (O(n * d))

You can avoid explicit sorting by counting how many times each digit (0–9) appears. A number can be reconstructed in non‑decreasing order by iterating through the digit frequency array from 0 to 9 and rebuilding the sequence. Because the digit range is fixed, counting runs in linear time relative to digit count. Each integer is processed in O(d) time with O(1) auxiliary space. This pattern appears often in problems involving frequency counting or greedy digit reconstruction.

Approach 4: Digit DP / Bitmask Validation (O(n * d * 10))

If additional constraints exist (for example, restrictions on leading zeros or positional rules), a digit dynamic programming approach can validate whether a sorted reconstruction is allowed. The digits are processed with state tracking for position and allowed digits. Although heavier than counting, this technique handles more complex rules while staying roughly linear in digit length. Space complexity typically remains O(d * 10) for the DP state.

Recommended for interviews: The digit frequency counting solution is usually the expected answer. Starting with the brute force permutation idea shows understanding of the definition, but recognizing that sorted order can be reconstructed directly using counts demonstrates stronger algorithmic thinking and reduces the complexity from factorial to linear per number.