We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Minimum Swaps 2
  2. Discussions

Minimum Swaps 2

Sort by

recency

|

2473 Discussions

|

  • weewee5931
     + 1 comment
    #include <bits/stdc++.h>

int main () {
    
    int n;
    std::cin >> n;
    
    std::vector<int> nums(n);
    for (auto& val : nums) {
        std::cin >> val;
        --val;
    }
    
    int ans = 0;
    for (int start = 0; start < n; ++start) {
        if (nums[start] == -1)
            continue;
            
        int streak = 0;
        for (int cur = start; nums[cur] != -1;) {
            ++streak;
            const int nei = nums[cur];
            nums[cur] = -1;
            cur = nei;
        }
        
        ans += streak - 1;
    }
    
    std::cout << ans << "\n";
    
    return 0;
}

  • lylia_luong
     + 0 comments

    simple python code. if u use for loop with this logic it won't work smh. 

    def minimumSwaps(arr):
    swaps = 0
    i = 0
    while i < len(arr):
        correct_value = i + 1
        if arr[i] != correct_value:
            swap_idx = arr[i] - 1  # Where this value should be
            arr[i], arr[swap_idx] = arr[swap_idx], arr[i]
            swaps += 1
        else:
            i += 1
    return swaps

  • prvz1122
     + 0 comments

    c++ code with simple concepts

    " bool checkZero(int num1 , int num2){ if(num1 - num2 == 1){ return true; } return false; } // Complete the minimumSwaps function below. int minimumSwaps(vector arr) { int size = arr.size();

    int temp =0 , swap = 0;
for(int i = 0; i < size ; i++){
    if(!checkZero(arr[i], i)){
        for(int j = i+1; j < size ;j++){

            if(checkZero(arr[j], i)){
                temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
                swap++;
                break;
            }
        }
    }
}
return swap;

    } "

  • czapaya
     + 0 comments

    I noticed that in Julia the code raises error for STDIN written with capital letters. Once I changed it to stdin, everything went smooth. So, I guess you should update the current version (unless I am missing something).

  • churknam
     + 0 comments

    Python code.

    Final ordered array should look like [1, 2, 3, ...], so we can iterate through the array and check if current value matches index+1. If they do not match, find the index of the value that matches index+1. Then swap the values at the current index and the other index and record the swap.

    Note: this code wouldn't work if the array isn't consecutive but it seems like all the test case arrays are consecutive now.

    def minimumSwaps(arr):
    temp = 0
    swap = 0
    for x in range(len(arr) - 1):
        if arr[x] != x + 1:
            min_index = arr.index(x + 1)
            temp = arr[x]
            arr[x] = x + 1
            arr[min_index] = temp
            swap += 1
    return swap