3551. Minimum Swaps to Sort by Digit Sum

/**
 * Problem: LeetCode 3551 - Minimum Swaps to Sort by Digit Sum
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */
import java.util.Arrays;

/**
 * Problem: LeetCode 3551 - Minimum Swaps to Sort by Digit Sum
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */
class Solution {
    public int minSwaps(int[] nums) {
        int n = nums.length;
        int[] ds = new int[n];
        for (int i = 0; i < n; i++) {
            int x = nums[i], s = 0;
            while (x > 0) {
                s += x % 10;
                x /= 10;
            }
            ds[i] = s;
        }
        Integer[] idx = new Integer[n];
        for (int i = 0; i < n; i++) idx[i] = i;
        Arrays.sort(idx, (a, b) -> {
            if (ds[a] != ds[b]) return Integer.compare(ds[a], ds[b]);
            return Integer.compare(nums[a], nums[b]);
        });
        boolean[] visited = new boolean[n];
        int swaps = 0;
        for (int i = 0; i < n; i++) {
            if (visited[i] || idx[i] == i) continue;
            int cycleLen = 0;
            int j = i;
            while (!visited[j]) {
                visited[j] = true;
                j = idx[j];
                cycleLen++;
            }
            swaps += cycleLen - 1;
        }
        return swaps;
    }
}

"""
Problem: LeetCode 3551 - Minimum Swaps to Sort by Digit Sum
Difficulty: Medium
Language: Python
Author: CodeByTushu
"""
from typing import List

class Solution:
    def minSwaps(self, nums: List[int]) -> int:
        def digit_sum(x: int) -> int:
            s = 0
            while x > 0:
                s += x % 10
                x //= 10
            return s

        n = len(nums)
        ds = [digit_sum(x) for x in nums]
        idx = sorted(range(n), key=lambda i: (ds[i], nums[i]))

        visited = [False] * n
        swaps = 0

        for i in range(n):
            if visited[i] or idx[i] == i:
                continue
            cycle_len = 0
            j = i
            while not visited[j]:
                visited[j] = True
                j = idx[j]
                cycle_len += 1
            swaps += cycle_len - 1

        return swaps

/**
 * Problem: LeetCode 3551 - Minimum Swaps to Sort by Digit Sum
 * Difficulty: Medium
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

/**
 * Problem: LeetCode 3551 - Minimum Swaps to Sort by Digit Sum
 * Difficulty: Medium
 * Language: C++
 * Author: CodeByTushu
 */
class Solution {
private:
    int getDigitSum(int x) {
        int s = 0;
        while (x > 0) {
            s += x % 10;
            x /= 10;
        }
        return s;
    }

public:
    int minSwaps(vector<int>& nums) {
        int n = nums.size();
        vector<int> ds(n);
        for (int i = 0; i < n; i++) {
            ds[i] = getDigitSum(nums[i]);
        }

        vector<int> idx(n);
        iota(idx.begin(), idx.end(), 0);
        sort(idx.begin(), idx.end(), [&](int a, int b) {
            if (ds[a] != ds[b]) return ds[a] < ds[b];
            return nums[a] < nums[b];
        });

        vector<bool> visited(n, false);
        int swaps = 0;

        for (int i = 0; i < n; i++) {
            if (visited[i] || idx[i] == i) continue;
            int cycleLen = 0;
            int j = i;
            while (!visited[j]) {
                visited[j] = true;
                j = idx[j];
                cycleLen++;
            }
            swaps += cycleLen - 1;
        }

        return swaps;
    }
};

/**
 * Problem: LeetCode 3551 - Minimum Swaps to Sort by Digit Sum
 * Difficulty: Medium
 * Language: JavaScript
 * Author: CodeByTushu
 */
var minSwaps = function(nums) {
    const n = nums.length;
    const ds = new Int32Array(n);

    for (let i = 0; i < n; i++) {
        let x = nums[i], s = 0;
        while (x > 0) {
            s += x % 10;
            x = Math.floor(x / 10);
        }
        ds[i] = s;
    }

    const idx = new Int32Array(n);
    for (let i = 0; i < n; i++) idx[i] = i;

    idx.sort((a, b) => {
        if (ds[a] !== ds[b]) return ds[a] - ds[b];
        return nums[a] - nums[b];
    });

    const visited = new Uint8Array(n);
    let swaps = 0;

    for (let i = 0; i < n; i++) {
        if (visited[i] || idx[i] === i) continue;
        let cycleLen = 0;
        let j = i;
        while (!visited[j]) {
            visited[j] = 1;
            j = idx[j];
            cycleLen++;
        }
        swaps += cycleLen - 1;
    }

    return swaps;
};