algorithm - Counting number of "BAD" values

问题描述

I was solving a problem and came across this one.

Suppose we have some clay balls. Each ball has a certain value; the value of each ball may be any positive integer. Initially, for each value between X and X+Y−1 (inclusive), we has an infinite supply of balls with this values.

The balls have a special property: any two of them can be mixed to create a new ball. If the original balls had values a and b (possibly a=b), the new ball has value a+b. The balls created this way may be used to mix other balls as well. We are free to mix balls in any way we choose any number of times.

Let's call a value v (v>0) BAD if there is no way to obtain a ball with value v; otherwise, value v is GOOD. We want to make balls with all GOOD values and we would like to know the number of BAD values.

Note : There is an infinite number of GOOD values of balls, but it can be proven that the number of BAD values is always finite for Y≥2.

For a given X and Y devise a procedure to find the number of BAD values.

E.g.

X = 1 ; Y = 2

We are given [1, 1 + 2 - 1] == [1, 2] == {1, 2} balls. Answer 0 ; As it is possible to obtain balls with all possible values as per X and Y.

X = 3 ; Y = 3

We are given [3, 3 + 3 - 1] == [3, 5] == {3, 4, 5} balls. Answer 2 ; As balls with values 1 and 2 cannot be made.

I thought that the values which are less than X cannot be made but it seems to be wrong, maybe I am missing something.

标签： algorithm

解决方案

When solving such problems, start from playing with numbers. Suppose we are given 2 balls (Y = 2), let them be 11 and 12 (X = 11). We can create

From 1 ball: 11, 12
From 2 balls: 22, 23, 24
From 3 balls: 33, 34, 35, 36
From 4 balls: 44, 45, 46, 47, 48

....

We have holes (bad numbers) however: 1..10 of size 10 then 13..21 of size 9 then 25..32 of size 8. Can you see the pattern? The sum of holes (number of bad numbers) is

10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 == 55

Now we can solve the problem if Y = 2: it's sum of arthimetic progression

X - 1 + X - 2 + ... + 2 + 1 == (X - 1) * (X - 2) / 2

Keep on doing on Y = 3, e.g. we are given 3 balls (Y = 3) 11, 12, 13 (X = 11). We can create:

From 1 ball: 11, 12, 13
From 2 balls: 22, 23, 24, 25, 26
From 3 balls: 33, 34, 35, 36, 37, 38, 39
From 4 balls: 44, 45, 46, 47, 48, 49, 50, 51, 52

Let's count holes: 1..10 then 14..21 then 26..33 followed by 40..43:

10 + 8 + 6 + 4 + 2 == 30

Can you see the pattern? Can you solve for Y = 3? Please, note the difference:

 X = 11; Y = 2   ->   10 + 9 + 8 + 7 + ... + 1
 X = 11; Y = 3   ->   10 + 8 + 6 + 4 + 2

Can you write the formula for Y = 3 now? For Y = 4, Y = 5?

 X = 11; Y = 4   ->   10 + 7 + 4 + 1
 x = 11; Y = 5   ->   10 + 6 + 2

For arbitrary Y?

 X = 11; Y       ->   10 + (10 - 1 * (Y - 1)) + (10 - 2 * (Y - 1)) + ...

For arbitrary X and Y (we have to sum all positive terms)?

 X; Y            ->   (X - 1) + (X - 1 - 1 * (Y - 1)) + (X - 1 - 2 * (Y - 1)) + ...

Code: Let it be C#:

private static int MySum(int X, int Y) {
  int d = Y - 1;                  // difference
  int n = (X - 1) / (Y - 1) + 1;  // number of items to sum

  int A1 = X - 1;                 // 1st item
  int An = X - 1 - (n - 1) * d;   // last item

  return (A1 + An) * n / 2;       // sum of arithmetic progression
}

Some tests (or demo):

(int, int)[] tests = new (int, int)[] {
   (X : 11, Y : 2),
   (X : 11, Y : 3),
   (X : 11, Y : 4),
   (X : 11, Y : 5),
   (X :  1, Y : 2),
   (X :  3, Y : 3),
};

string demo = string.Join(Environment.NewLine, tests
  .Select(test => $"X = {test.Item1,2}, Y = {test.Item2} => {MySum(test.Item1, test.Item2),2}"));

Console.Write(demo);

Outcome:

X = 11, Y = 2 => 55
X = 11, Y = 3 => 30
X = 11, Y = 4 => 22
X = 11, Y = 5 => 18
X =  1, Y = 2 =>  0 // test from the question
X =  3, Y = 3 =>  2 // test from the question

algorithm - Counting number of "BAD" values

问题描述

解决方案

推荐阅读