CODEWITHSUNDEEP
javascriptarraysalgorithmdart
Danil Shubin
Danil Shubin

Reputation: 11

Make the sum of array values equal to k

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:

  1. array - array of latin characters, 0<length(array)<20, sub_array[i]="x" | "y" | "z"
  2. k - the value of the sum of the array to be obtained, 0<k<150

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]

Upvotes: 1

Views: 518

Answers (3)

Carsten Massmann
Carsten Massmann

Reputation: 28206

Here is a simple solution that works on the assumptions that:

  • a number can be assigned to at most one character
  • there is at least one character that occurs only once

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, false

Obviously 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.

Upvotes: 0

maraca
maraca

Reputation: 8773

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.

Upvotes: 1

Marat
Marat

Reputation: 15738

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

Upvotes: 1

Related Questions