CODEWITHSUNDEEP
c++arraysalgorithmsorting
User
User

Reputation: 67

Getting wrong number of swaps for the algorithm problem

Problem

Whenever George asks Lily to hang out, she's busy doing homework. George wants to help her finish it faster, but he's in over his head! Can you help George understand Lily's homework so she can hang out with him?

Consider an array of n distinct integers, arr=[a[0],...,a[n-1]] . George can swap any two elements of the array any number of times. An array is beautiful if the sum of |a[i]-a[i-1]| > 0 among 0 < i < n is minimal.

Given the array arr, determine and return the minimum number of swaps that should be performed in order to make the array beautiful.

For example, arr = [7,15,12,3]. One minimal array is [3, 7, 12, 15]. To get there, George performed the following swaps:

Swap      Result
          [7, 15, 12, 3]
3 7       [3, 15, 12, 7]
7 15      [3, 7, 12, 15]

It took 2 swaps to make the array beautiful. This is minimal among the choice of beautiful arrays possible.

Input Format

The first line contains a single integer n , the number of elements in arr . The second line contains n  space-separated integers arr[i].

Constraints

0 < n < 100001 0 < arr[i] < 2000000001

Output Format

Return the minimum number of swaps needed to make the array beautiful.

Sample Input

4 2 5 3 1

Sample Output

2

My effort

I calculate the number of swaps comparing arr elements with its version sorted in the ascending and descending order. But for some reason, I'm getting the wrong result.

Code

int findSwaps(vector<int>& arr, const vector<int>& sortedArr, std::map<int, int> arrIndexMap) {
    int swaps = 0;
    int size = arr.size();

    for (int i = 0; i < size; i++) {
        if (arr[i] != sortedArr[i]) {
            swaps++;

            int j = arrIndexMap[sortedArr[i]];
            arrIndexMap[arr[i]] = j;
            arrIndexMap[arr[j]] = i;

            arr[j] = arr[i];
            arr[i] = sortedArr[i];
        }
    }

    return swaps;
}

int main() {
    int n;
    cin >> n;
    std::vector<int> arr(n);

    for (int i = 0; i < n; i++) {
        int value;
        cin >> value;
        arr.push_back(value);
    }

    std::map<int, int> arrIndexMap;
    for (int i = 0; i < n; i++) {
        arrIndexMap[arr[i]] = i;
    }

    std::vector<int> sortedArr = arr;
    std::sort(sortedArr.begin(), sortedArr.end());

    std::vector<int> descSortedArr = arr;
    std::sort(descSortedArr.begin(), descSortedArr.end(), std::greater<>());

    int swaps1 = findSwaps(arr, sortedArr, arrIndexMap);
    int swaps2 = findSwaps(arr, descSortedArr, arrIndexMap);
    cout << std::min(swaps1, swaps2);

    return 0;
}

Input

5
3 4 2 5 1

Expected Output

2

Actual Output

5

Upvotes: 1

Views: 674

Answers (1)

Anatolii
Anatolii

Reputation: 14660

Your algorithm is actually correct. However, there’re 2 C++ problems that lead to the unexpected behaviour:

1. You initialise your arr vector with n elements equal to 0 here:

std::vector<int> arr(n);

And then you add n additional elements in a loop.

But you must have only n elements in your arr as per problem statement. So, create an empty vector by default:

std::vector<int> arr;

2. Another issue is that you pass your arr by reference and that’s why the second time you pass it to findSwaps(...), it's already a modified version from your first call:

So, you should pass it by value so that not to affect the initial arr:

int findSwaps(vector<int> arr, const vector<int>& sortedArr, std::map<int, int> arrIndexMap)

After these 2 changes, I've tried your code on Hackerrank and it has passed all the tests.

Upvotes: 3

Related Questions