I came across an algorithmic problem and I can’t figure out how to solve it in principle, because I didn’t find any of the algorithms that could be used here. Maybe someone can help me with this.
Task: There is an array of latin characters. Each character in the array can be replaced by any integer number. After the replacement, all identical characters will also be replaced by the same number. Is it possible to make the sum of the array values equal to k?
Input:
Output: Boolean - you can or cannot make the sum of the values of the array array equal to k
Example (Dart):
var array = ["x", "x", "x", "y", "z"];
var k = 10;
print(getResult(array, k)); // return true, because [2, 2, 2, 3, 1]
First you can go through the array and count the number of occurences of "x", "y" and "z". I will call those counts x, y and z. Then the problem becomes:
Can you find integers a, b and c such that a * x + b * y + c * z = k.
If the numbers can be negative then it is relatively simple: it is possible if k % gcd(x, y, z) = 0 (ignoring 0s, so if x is 0 then k % gcd(y, z) = 0). In other words it is only possible to fail if you can just make multiples of gcd(x, y, z) and k is not a multiple of those numbers.
If a, b and c have to be non-negative, then it becomes a little bit more complex. We are dealing with the coin problem with currencies x, y and z. If k % gcd(x, y, z) != 0 then it is never possible. Now we could simplify the problem by dividing k, x, y and z by gcd(x, y, z). After that we can see if it is easily possible by using the Frobenius numbers:
n = 2: all numbers > x * y - x - y can be built
n = 3: all numbers > sqrt(3 * x * y * z) can be built
If k is smaller than that we can check if k can be built by using the common dynamic programming solution for the coin problem.
Of course there are some edge cases you have to deal with. E.g. k = 0 or if there is only one number given, then it is just k % x = 0.
Observation: given n x, m y, etc, by changing either of x,y,... values by one, the sum can be changed only in GCD(n, m, ...) increments, where GCD is the greatest common divisor (can be found with Euclid algorithm).
Thus, the condition can be satisfied only when k is a multiple of their quantities GCD.
Note: this assumes x, y, ... might not be unique, and can be negative
Here is a simple solution that works on the assumptions that:
function findNumbers([s,sum]) { // count occurences of characters:
let ar1 = Object.entries(s.split("").reduce((a, c) => (a[c] = (a[c] || 0) + 1, a), {}))
.sort((a, b) => b[1] - a[1]); // sort: most frequent characters first
// assign interger values to each character (starting with 1 ...
let ar2=ar1.map(([c, n], i) =>{ // c: character, n: occurences, i: index
sum-=n*(i+1);
return [c, i+1<ar1.length? i+1: ar1.length+sum]
});
return [Object.fromEntries(ar2),ar2.pop()[1]>ar2.pop()[1]]; // add a results flag to each solution: true/false
}
let res=[["xxxyz",10],["ghijjk",17],["abcabcabd",12],["abccdef",18],["abcd",9]].map(findNumbers)
console.log(res) // true, true, false, false, falseObviously this was a fast shot. I do not yet check whether the least frequent character only occurs once. It certainly needs more refinement but it indicates already pretty quickly whether a solution with positive integers would be possible. If the last number is not greater then the penultimate one, suitable numbers cannot be found and the false flag is returned.