Minimize count of divisions by D to obtain at least K equal array elements | HARD | OA | READ IT

https://www.geeksforgeeks.org/minimize-count-of-divisions-by-d-to-obtain-at-least-k-equal-array-elements/

Given an array A[ ] of size N and two integers K and D, the task is to calculate the minimum possible number of operations required to obtain at least K equal array elements. Each operation involves replacing an element A[i] by A[i] / D. This operation can be performed any number of times.

Examples:

Input: N = 5, A[ ] = {1, 2, 3, 4, 5}, K = 3, D = 2
Output: 2
Explanation:
Step 1: Replace A[3] by A[3] / D, i.e. (4 / 2) = 2. Hence, the array modifies to {1, 2, 3, 2, 5}
Step 2: Replace A[4] by A[4] / D, i.e. (5 / 2) = 2. Hence, the array modifies to {1, 2, 3, 2, 2}
Hence, the modified array has K(= 3) equal elements.
Hence, the minimum number of operations required is 2.


Input: N = 4, A[ ] = {1, 2, 3, 6}, K = 2, D = 3
Output: 1
Explanation:
Replacing A[3] by A[3] / D, i.e. (6 / 3) = 2. Hence, the array modifies to {1, 2, 3, 2}.
Hence, the modified array has K(= 2) equal elements.
Hence, the minimum number of operations required is 1.


---------------------------------------------------------------------------------------------------------------------------------------

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;

// Function to return minimum
// number of moves required
int getMinimumMoves(int n, int k, int d,
                    vector<int> a)
{
    int MAX = 100000;

    // Stores the number of moves
    // required to obtain respective
    // values from the given array
    vector<int> v[MAX];

    // Traverse the array
    for (int i = 0; i < n; i++) {
        int cnt = 0;

        // Insert 0 into V[a[i]] as
        // it is the initial state
        v[a[i]].push_back(0);

        while (a[i] > 0) {
            a[i] /= d;
            cnt++;

            // Insert the moves required
            // to obtain current a[i]
            v[a[i]].push_back(cnt);
        }
    }

    int ans = INT_MAX;

    // Traverse v[] to obtain
    // minimum count of moves
    for (int i = 0; i < MAX; i++) {

        // Check if there are at least
        // K equal elements for v[i]
        if (v[i].size() >= k) {

            int move = 0;

            sort(v[i].begin(), v[i].end());

            // Add the sum of minimum K moves
            for (int j = 0; j < k; j++) {

                move += v[i][j];
            }

            // Update answer
            ans = min(ans, move);
        }
    }

    // Return the final answer
    return ans;
}

// Driver Code
int main()
{
    int N = 5, K = 3, D = 2;
    vector<int> A = { 1, 2, 3, 4, 5 };

    cout << getMinimumMoves(N, K, D, A);

    return 0;
}