CODEWITHSUNDEEP
c++algorithmdata-structures
TriposG
TriposG

Reputation: 113

Solving Minimum swaps hackerrank question in C++

I have a question about the Minimum Swap question on Hackerrank.

Basically the question is to find the number of swaps required to sort the array.

The array doesn't contain any duplicated elements.

Here is my code but I seem to get a wrong answer. Particularly, I get 4 times the array length for the vector temp.

int minimumSwaps(vector<int> arr) {

int n = arr.size();
int count_swap = 0;

vector<int> temp;

for(int i = 0; i < n; ++i){
    cout << temp.size()<<"\n";
    if(arr[i] == i+1){

        temp.push_back(arr[i]);
    }

    else{

        int initial_val = arr[i];

        int next_val = arr[arr[i] - 1];

        temp.push_back(initial_val);

        while(next_val != initial_val){

            temp.push_back(next_val);

            next_val = arr[next_val - 1];

            count_swap += 1;
            }
        }
    if (temp.size() == n){
        break;
    }      

}
print(temp);
return count_swap;


}

My approach was to find a cyclic loop in the array and the min number of swaps required is that number - 1.

So for example, if we have arr = [2,3,4,1,5]

2 -> 3 -> 4 -> 1 -> 2

So there is a loop of length 4. Hence the min swap required is 4-1 =3. (Since the other 5 is already in place and will have loop length =1 hence 0 swaps required).

Upvotes: 0

Views: 1268

Answers (1)

MannyC
MannyC

Reputation: 46

The algorithm iterates over each element in the vector, and then proceeds to determine the cycle at that element. It therefore encounters the first cycle four times. The algorithm should likely iterate over the cycles in the vector instead.

Upvotes: 0

Related Questions