# Minimum Swaps to Sort by Digit Sum
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-swaps-to-sort-by-digit-sum)
Canonical: https://scaleengineer.com/dsa/problems/minimum-swaps-to-sort-by-digit-sum
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
---
## Problem
You are given an array `nums` of **distinct** positive integers. You need to sort the array in **increasing** order based on the sum of the digits of each number. If two numbers have the same digit sum, the **smaller** number appears first in the sorted order.

Return the **minimum** number of swaps required to rearrange `nums` into this sorted order.

A **swap** is defined as exchanging the values at two distinct positions in the array.

**Example 1:**

**Input:** nums = \[37,100\]

**Output:** 1

**Explanation:**

* Compute the digit sum for each integer: `[3 + 7 = 10, 1 + 0 + 0 = 1] → [10, 1]`
* Sort the integers based on digit sum: `[100, 37]`. Swap `37` with `100` to obtain the sorted order.
* Thus, the minimum number of swaps required to rearrange `nums` is 1.

**Example 2:**

**Input:** nums = \[22,14,33,7\]

**Output:** 0

**Explanation:**

* Compute the digit sum for each integer: `[2 + 2 = 4, 1 + 4 = 5, 3 + 3 = 6, 7 = 7] → [4, 5, 6, 7]`
* Sort the integers based on digit sum: `[22, 14, 33, 7]`. The array is already sorted.
* Thus, the minimum number of swaps required to rearrange `nums` is 0.

**Example 3:**

**Input:** nums = \[18,43,34,16\]

**Output:** 2

**Explanation:**

* Compute the digit sum for each integer: `[1 + 8 = 9, 4 + 3 = 7, 3 + 4 = 7, 1 + 6 = 7] → [9, 7, 7, 7]`
* Sort the integers based on digit sum: `[16, 34, 43, 18]`. Swap `18` with `16`, and swap `43` with `34` to obtain the sorted order.
* Thus, the minimum number of swaps required to rearrange `nums` is 2.

**Constraints:**

* `1 <= nums.length <= 105`
* `1 <= nums[i] <= 109`
* `nums` consists of **distinct** positive integers.

# Approaches
## Brute-Force Swapping (Selection Sort Variant)
This approach first determines the final sorted state of the array. Then, it iterates through a copy of the original array, and for each position, if the element is incorrect, it finds the correct element and swaps it into place, counting each swap. This is analogous to a Selection Sort.
**Time:** O(N^2) - The dominant operation is the nested loop structure. The outer loop runs N times, and the inner linear search for the correct element can take up to O(N) time in each iteration. The initial sort takes O(N log N), but it's overshadowed by the O(N^2) swapping part. · **Space:** O(N) - We need to store a copy of the array and the target sorted array.
**Pros:** Conceptually simple and easy to implement.; Directly simulates the process of sorting by swapping elements into their final positions.
**Cons:** Highly inefficient with a quadratic time complexity.; Will result in a 'Time Limit Exceeded' error for the given problem constraints (N up to 10^5).
### Explanation
The core idea is to simulate the sorting process using the minimum number of swaps possible, which is what Selection Sort does. First, we need to know the target state, so we create a sorted version of the array, `sortedNums`, according to the specified rules (digit sum, then value).

Then, we take a copy of the original array, `numsCopy`, and iterate through it. For each index `i`, we check if the element `numsCopy[i]` is the one that should be there, i.e., if `numsCopy[i] == sortedNums[i]`. If it's not, we know a swap is necessary. We find the correct element (`sortedNums[i]`) somewhere else in the array (at an index `j > i`) and swap it with the element at `i`. We increment our swap counter for each such exchange.

The main drawback is the search for the correct element at each step, which requires a linear scan of the rest of the array, leading to an overall quadratic time complexity.

```java
import java.util.Arrays;

class Solution {
    private int getDigitSum(int n) {
        int sum = 0;
        while (n > 0) {
            sum += n % 10;
            n /= 10;
        }
        return sum;
    }

    public int minimumSwaps(int[] nums) {
        int n = nums.length;
        Integer[] sortedNumsInteger = new Integer[n];
        for (int i = 0; i < n; i++) {
            sortedNumsInteger[i] = nums[i];
        }

        Arrays.sort(sortedNumsInteger, (a, b) -> {
            int sumA = getDigitSum(a);
            int sumB = getDigitSum(b);
            if (sumA != sumB) {
                return Integer.compare(sumA, sumB);
            } else {
                return Integer.compare(a, b);
            }
        });

        int[] sortedNums = new int[n];
        for (int i = 0; i < n; i++) {
            sortedNums[i] = sortedNumsInteger[i];
        }

        int[] numsCopy = Arrays.copyOf(nums, n);
        int swaps = 0;

        for (int i = 0; i < n; i++) {
            if (numsCopy[i] != sortedNums[i]) {
                swaps++;
                for (int j = i + 1; j < n; j++) {
                    if (numsCopy[j] == sortedNums[i]) {
                        int temp = numsCopy[i];
                        numsCopy[i] = numsCopy[j];
                        numsCopy[j] = temp;
                        break;
                    }
                }
            }
        }
        return swaps;
    }
}
```
### Algorithm
- Define a helper function `getDigitSum(int n)` to calculate the sum of digits.
- Create a copy of the input array, `numsCopy`.
- Create the target sorted array, `sortedNums`, by sorting `nums` based on the custom rule (digit sum, then value).
- Initialize `swaps = 0`.
- Iterate through `numsCopy` from `i = 0` to `n-1`.
- If `numsCopy[i]` is not equal to `sortedNums[i]`:
    - Increment `swaps`.
    - Linearly search for `sortedNums[i]` in `numsCopy` from index `i+1`. Let its index be `j`.
    - Swap `numsCopy[i]` and `numsCopy[j]`.
- Return `swaps`.

## Optimal Approach: Graph Cycle Counting
This problem can be reframed as finding the minimum number of swaps to sort a permutation. The minimum number of swaps is given by the formula `N - C`, where `N` is the number of elements and `C` is the number of disjoint cycles in the permutation. The approach involves determining the permutation that maps each element from its original position to its sorted position and then counting the cycles in this permutation graph.
**Time:** O(N log N) - The main bottleneck is sorting the array of pairs. Calculating digit sums for all elements takes O(N * log K) (where K is the maximum value of a number), and counting cycles takes O(N). Thus, the overall complexity is dominated by the sort. · **Space:** O(N) - We need space to store the list of pairs, a cache for digit sums, and the `visited` array for cycle counting.
**Pros:** Optimal time complexity for this problem.; Guaranteed to find the minimum number of swaps.; Handles large inputs efficiently.
**Cons:** More complex to conceptualize and implement than the naive approach.; Requires understanding of permutation cycles.
### Explanation
This optimal approach leverages a classic result from combinatorics. The minimum number of swaps to sort any permutation of `N` elements is `N - C`, where `C` is the number of disjoint cycles in the permutation.

First, we need to figure out where each element is supposed to go. We can do this by creating pairs of `(value, originalIndex)` and sorting these pairs based on the problem's custom sorting rule. After sorting, if we look at the `i`-th pair, its `value` is what should be at index `i` in the final array, and its `originalIndex` tells us where this value came from.

This gives us a permutation graph where an edge exists from an element's original position to its final position. We can count the number of disjoint cycles in this graph. A cycle is a path that starts and ends at the same index, e.g., `A -> B -> C -> A`. The number of swaps needed to fix a cycle of length `k` is `k-1`.

We can count cycles by iterating through all indices from `0` to `N-1`. If we find an index that we haven't visited yet, we've found a new cycle. We then traverse this cycle, marking all its nodes as visited, and increment our cycle counter. The final answer is `N - totalCycles`.

```java
import java.util.*;

class Solution {
    private int getDigitSum(int n) {
        int sum = 0;
        int temp = n;
        while (temp > 0) {
            sum += temp % 10;
            temp /= 10;
        }
        return sum;
    }

    class Pair {
        int value;
        int originalIndex;

        Pair(int value, int originalIndex) {
            this.value = value;
            this.originalIndex = originalIndex;
        }
    }

    public int minimumSwaps(int[] nums) {
        int n = nums.length;
        List<Pair> indexedNums = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            indexedNums.add(new Pair(nums[i], i));
        }

        // A cache for digit sums can optimize the sorting comparison,
        // as getDigitSum might be called multiple times for the same number.
        Map<Integer, Integer> digitSumCache = new HashMap<>();

        Collections.sort(indexedNums, (p1, p2) -> {
            int sum1 = digitSumCache.computeIfAbsent(p1.value, this::getDigitSum);
            int sum2 = digitSumCache.computeIfAbsent(p2.value, this::getDigitSum);
            
            if (sum1 != sum2) {
                return Integer.compare(sum1, sum2);
            } else {
                return Integer.compare(p1.value, p2.value);
            }
        });

        boolean[] visited = new boolean[n];
        int totalCycles = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                totalCycles++;
                int j = i;
                while (!visited[j]) {
                    visited[j] = true;
                    // Follow the cycle: the element that should be at sorted position 'j'
                    // came from original position 'indexedNums.get(j).originalIndex'.
                    j = indexedNums.get(j).originalIndex;
                }
            }
        }

        return n - totalCycles;
    }
}
```
### Algorithm
- Create a list of pairs, `(value, originalIndex)`, for each element in the input array.
- Sort this list based on the custom rule: primarily by the digit sum of the number (ascending), and secondarily by the number itself (ascending).
- The sorted list implicitly defines a permutation. The element at original index `p.originalIndex` moves to the new index `i` where `p` is `sortedList.get(i)`.
- To find the minimum swaps, count the number of cycles in this permutation. Initialize a `visited` array of size `N`.
- Iterate from `i = 0` to `n-1`. If `i` has not been visited, start a traversal from `i`, following the permutation links and marking nodes as visited, until you return to the start. This completes one cycle. Increment a cycle counter.
- The minimum number of swaps is `N - numberOfCycles`.

# Solutions
### Java

```java
class Solution {
public
  int minSwaps(int[] nums) {
    int n = nums.length;
    int[][] arr = new int[n][2];
    for (int i = 0; i < n; i++) {
      arr[i][0] = f(nums[i]);
      arr[i][1] = nums[i];
    }
    Arrays.sort(
        arr, (a, b)->{
          if (a[0] != b[0])
            return Integer.compare(a[0], b[0]);
          return Integer.compare(a[1], b[1]);
        });
    Map<Integer, Integer> d = new HashMap<>();
    for (int i = 0; i < n; i++) {
      d.put(arr[i][1], i);
    }
    boolean[] vis = new boolean[n];
    int ans = n;
    for (int i = 0; i < n; i++) {
      if (!vis[i]) {
        ans--;
        int j = i;
        while (!vis[j]) {
          vis[j] = true;
          j = d.get(nums[j]);
        }
      }
    }
    return ans;
  }
private
  int f(int x) {
    int s = 0;
    while (x != 0) {
      s += x % 10;
      x /= 10;
    }
    return s;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int f(int x) {
    int s = 0;
    while (x) {
      s += x % 10;
      x /= 10;
    }
    return s;
  }
  int minSwaps(vector<int> &nums) {
    int n = nums.size();
    vector<pair<int, int>> arr(n);
    for (int i = 0; i < n; ++i)
      arr[i] = {f(nums[i]), nums[i]};
    sort(arr.begin(), arr.end());
    unordered_map<int, int> d;
    for (int i = 0; i < n; ++i)
      d[arr[i].second] = i;
    vector<char> vis(n, 0);
    int ans = n;
    for (int i = 0; i < n; ++i) {
      if (!vis[i]) {
        --ans;
        int j = i;
        while (!vis[j]) {
          vis[j] = 1;
          j = d[nums[j]];
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minSwaps(self, nums: List[int]) -> int: def f(x: int) -> int: s = 0 while x: s += x % 10 x //= 10 return s n = len(nums) arr = sorted((f(x), x) for x in nums) d = {a[1]: i for i, a in enumerate(arr)} ans = n vis = [False] * n for i in range(n): if not vis[i]: ans -= 1 j = i while not vis[j]: vis[j] = True j = d[nums[j]] return ans

```