algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

minimum-swaps-to-sort-by-digit-sum.cpp (1454B)


      1 int sumDigits(int input) {
      2     int res = 0;
      3     
      4     while(input > 0) {
      5         res += (input % 10);
      6         input /= 10;
      7     }
      8     return res;
      9 }
     10 
     11 std::string encodePair(std::pair<int,int> pr) {
     12     return std::to_string(pr.first) + ":" + std::to_string(pr.second);
     13 }
     14 
     15 class Solution {
     16 public:
     17     int minSwaps(vector<int>& nums) {
     18 
     19         std::vector<std::pair<int,int>> pairs {};
     20         std::vector<std::pair<int,int>> sortedPairs {};
     21 
     22 
     23         for(int i = 0; i < nums.size(); ++i) {
     24             pairs.push_back({sumDigits(nums[i]), nums[i]});
     25             sortedPairs.push_back({sumDigits(nums[i]), nums[i]});
     26         }
     27 
     28         std::sort(sortedPairs.begin(), sortedPairs.end());
     29 
     30         std::unordered_map<std::string,int> h {};
     31 
     32         for(int i = 0; i < pairs.size(); ++i) {
     33             h[encodePair(pairs[i])] = i;
     34         }
     35 
     36         int swapCount = 0;
     37         for(int i = 0; i < pairs.size(); ++i) {
     38 
     39             if(pairs[i] != sortedPairs[i]) {
     40                 std::string encodedBase = encodePair(pairs[i]);
     41                 std::string encodedTarget = encodePair(sortedPairs[i]);
     42 
     43                 int swapIndex = h[encodedTarget];
     44 
     45                 auto temp = pairs[i];
     46                 pairs[i] = pairs[swapIndex];
     47                 pairs[swapIndex] = temp;
     48 
     49                 h[encodedTarget] = i;
     50                 h[encodedBase] = swapIndex;
     51 
     52                 swapCount += 1;
     53             }
     54         }
     55         
     56 
     57         return swapCount;
     58     }
     59 };