Hello Readers!

In this blog, we will solve sorting and searching problems from the CSES problem set. We will solve some problems and try to understand the logic behind them, and how the idea of sorting can be used to solve various kinds of problems.

Distinct Numbers

This is the first problem in the sorting

and searching section. This is a simple problem that asks us to calculate the number of distinct values in the array. Now, we can simply use a set or map to solve this problem. But since this problem comes under the sorting section, let's try to use that.

Once you sort the array, all the equal values will be next to each other and we can simply use that fact to calculate the number of distinct numbers. If for some positions i and i + 1 values are equal the total distinct number will be reduced by 1. So we can simply calculate this count and subtract it from the size of the array.

#include<bits/stdc++.h>
using namespace std;

int main() {
    int arrSize;
    cin >> arrSize;
    vector<int> arr(arrSize);
    for(int i = 0; i < arrSize; i++) {
        cin >> arr[i];
    }

    sort(arr.begin(), arr.end());

    int countOfPosition = 0;
    for(int i = 1; i < arrSize; i++) {
        if(arr[i] == arr[i - 1]) {
            countOfPosition++;
        }
    }

    cout << (arrSize - countOfPosition) << endl;
    return 0;
}

Apartments

In this problem, you are given n applicants and m free apartments. We are also given the desired size of each applicant and the size of each apartment. The main task is to distribute as many apartments as we can. Each application can accept an apartment that is close enough to the desired size.

NOTE: In this problem close enough is defined as the range from desired size - k to desired size + k. (k is given and different for each problem)

In this problem, we will sort both the desired size and the size of the apartments. And we will use two pointer approach where we will try to allocate each applicant with his desired apartment size. One thing you can easily notice as we have sorted both arrays, the apartment we allocate to an applicant (if we do) is the least size he can get. It is a necessary condition to work out our greedy approach.

Now, we need to check if our current apartment size is okay for our applicant if it is less than his need then we need to check for a different apartment, and if it is greater than his need we need to skip this applicant and move ahead. (as all apartments are in sorted order).

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n, m, k;
    cin >> n >> m >> k;

    vector<int> desiredSize(n), apartmentSize(m);
    for(int i = 0; i < n; i++) {
        cin >> desiredSize[i];
    }   
    for(int i = 0; i < m; i++) {
        cin >> apartmentSize[i];
    }

    sort(desiredSize.begin(), desiredSize.end());
    sort(apartmentSize.begin(), apartmentSize.end());

    int allocated = 0;
    int idx = 0;
    for(int i = 0; i < n; i++) {       
        int mxSize = desiredSize[i] + k;
        int mnSize = desiredSize[i] - k;

        /*
            Iterating apartmentSize array for the desired size.
        */
        while(idx < m and apartmentSize[idx] < mnSize) {
            idx++;
        }

        /*
            We have traversed entire apartmentSize array.
        */
        if(idx == m) {
            break;
        }

        /*
            We don't have any free apartments for this applicant.
        */
        if(apartmentSize[idx] > mxSize) {
            continue;
        } 

        /*
            We have allocated a free apartment to applicant.
        */
        allocated++;
        idx++;
    }

    cout << allocated << endl;
    return 0;
}

Ferris Wheel

In this problem, we are required to fit each child in a gondola(a light flat-bottomed boat). Each gondola can contain almost two children and can not have a weight exceeding X. What is the minimum number of gondolas required?

Now, we can observe one thing here, if want to keep two children in a gondola then their weight difference should be as maximum as possible. We can do this by checking if we can place kids with maximum and minimum weight in the same gondola and if we can't then we will keep the kid with maximum weight on the gondola. After that, we will check if we can keep kids with minimum weight and second maximum weight in the same boat. We will continuously do that until no kid remains.

We can do this by sorting the array and taking two pointers l and r, and checking if the summation of numbers in both places exceeds x. If it does increase the count by 1 and decrement r by 1. Then continue to check l and r until l < r.

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n, x;
    cin >> n >> x;

    vector<int> weight(n);
    for(int i = 0; i < n; i++) {
        cin >> weight[i];
    }

    sort(weight.begin(), weight.end());

    int countGondola = 0;
    int l = 0, r = n - 1;
    while(l <= r) {
        if(l == r) {
            l++;
        } else if(weight[l] + weight[r] <= x) {
            l++, r--;
        } else {
            r--;
        }
        countGondola++;
    }

    cout << countGondola << endl;
    return 0;
}

If you have any doubt please contact below.