Minimum Swaps for Digit-Sum Order
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# Minimum Swaps for Digit-Sum Order
You are given an array `nums` of distinct positive integers. Its required order is increasing decimal digit sum. When two values have the same digit sum, the smaller numeric value must come first.
Return the minimum number of swaps needed to put the array in this order. One swap exchanges the values at any two different positions; the positions need not be adjacent. Return only the minimum count.
### C++ Interface
```cpp
class Solution {
public:
int minSwaps(vector<int>& nums);
};
```
### Examples
**Example 1**
```text
nums = [40,12,3]
Output: 1
```
The digit sums are `[4,3,3]`, so the required array is `[3,12,40]`. For equal digit sum three, value three precedes value twelve. Exchanging the first and last positions gives the required order in one swap; zero swaps cannot work because the original order differs.
**Example 2**
```text
nums = [24,1,13,2]
Output: 2
```
The required order is `[1,2,13,24]`. Swap positions `0` and `1`, then positions `1` and `3`, to obtain it. Initially positions `0`, `1`, and `3` are incorrect; one swap can change only two positions, so a single swap cannot suffice.
### Constraints
- `1 <= nums.length <= 100000`.
- `1 <= nums[i] <= 1000000000`.
- All values in `nums` are distinct.
### Clarifying Questions
- Does a swap have to use neighboring positions? No. Any two distinct positions may be exchanged.
- Must equal-digit-sum values keep their original relative order? No. Their numeric values determine the required order.
- Can the digit sums repeat even though the values are distinct? Yes. For example, three and twelve both have digit sum three.
- Should the function return the reordered array? No. It returns the minimum swap count.
### What a Strong Answer Covers
- The full ordering rule, including the numeric tie-break for equal digit sums.
- A minimum count for unrestricted swaps rather than a count of adjacent exchanges.
- Correct results for singleton arrays and arrays already in the required order.
- A proof that no smaller unrestricted-swap count works, and resource bounds for up to 100000 distinct values.
### Follow-up Questions
- If every value has the same digit sum, what final ordering is required?
- Can two initial arrangements of the same values require different minimum swap counts? Give an example.
```hint Track destinations
Sort records by digit sum and then numeric value, retaining each value's original position. Map each original position to its required destination. This mapping is a permutation; consider how many swaps are needed for each of its cycles.
```
Overview: Find the minimum number of unrestricted swaps needed to order distinct positive integers by digit sum, breaking equal sums by numeric value. Return the count for the original arrangement.
