Being Code Expert: Old keypad in a foreign land

Some people remain old-fashioned and John is one of them. He doesn't like the new smartphones with full keypads and still uses the old keypads which require you to tap the key multiple times to type a single letter. For example, if the keyboard has two keys, one with the letters "adef" and the other one with the letters "zyx", then typing 'a' requires one keystroke, typing 'f' requires four keystrokes, typing 'y' requires two keystrokes, and so on.

He recently moved to a new country where the language is such that his keypad is not the most efficient. In every language, some characters occur more often than others. He wants to create a specific keyboard for this language that uses N different letters. He has a large body of text in this language and has already analyzed it to find the frequencies of all N letters of its alphabet.

You are given an array 'frequencies' with N elements. Each element of frequencies is the number of times one of the letters in the new language appears in the text John has. Each element of frequencies will be strictly positive. (I.e., each of the N letters occurs at least once.)

You are also given an array keySize. The number of elements of keySize is the number of keys on the keyboard. Each element of keySize gives the maximal number of letters that may be put on one of the keys.

Find an assignment of letters to keys that minimizes the number of keystrokes needed to type the entire text. An output that the minimum number of keystrokes. If there is not enough room on the keys and some letters of the alphabet won't fit, Output -1 instead.

Example:

Input:  n = 4, a[n] = {7, 3, 4, 1}, k = 2, b[k] = {2, 2}
Output: 19

Approach

Java

import java.util.Arrays;
import java.util.Vector;

public class OldKeyPad {
    public static void main(String[] args) {

        int n = 4;
        int a[] = { 7, 3, 4, 1 };

        int k = 2;
        int b[] = { 2, 2 };

        oldKeypad(n, a, k, b);

    }

    static void oldKeypad(int n, int a[], int k, int b[]) {
        Arrays.sort(a);
        Arrays.sort(b);

        int cnt = 0;
        Vector<int[]> v = new Vector<int[]>();
        int l = 1, m = n - 1;
        int res = 0;
        int sum = 0;
        for (int i = 0; i < k; i++)
            sum += b[i];
        if (sum < n)
            System.out.println(-1);
        else {
            while (cnt != n && m >= 0) {
                for (int i = 0; i < k && m >= 0; i++) {
                    if (b[i] > 0) {
                        b[i]--;
                        cnt++;
                        int e[] = { a[m--], l };
                        v.add(e);
                    }
                }
                l++;
            }
            for (int i = 0; i < v.size(); i++)
                res += v.get(i)[0] * v.get(i)[1];
            System.out.println(res);
        }
    }

}

C++

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

void oldKeypad(int n, int a[],
               int k, int b[])
{
    sort(a, a + n);
    sort(b, b + k);
    int cnt = 0;
    vector<pair<int, int>> v;
    int l = 1, m = n - 1;
    int res = 0;
    int sum = 0;
    for (int i = 0; i < k; i++)
        sum += b[i];
    if (sum < n)
        cout << -1 << "\n";
    else
    {
        while (cnt != n && m >= 0)
        {
            for (int i = 0; i < k && m >= 0; i++)
            {
                if (b[i])
                {
                    b[i]--;
                    cnt++;
                    v.push_back({a[m--], l});
                }
            }
            l++;
        }
        for (int i = 0; i < v.size(); i++)
            res += v[i].first * v[i].second;
        cout << res << "\n";
    }
}
int main()
{
    int n = 4;
    int a[n] = {7, 3, 4, 1};

    int k = 2;
    int b[k] = {2, 2};

    oldKeypad(n, a, k, b);

    return 0;
}