The number of ones#44

The number of ones (Editorial)

Let $f (n)$ denote the minimum number of ones needed to represent the number $n$ . Clearly, $f (1) = 1$ f(1) = 1.

The number $2$ can only be represented as the sum of two ones: $2 = 1 + 1$ 2 = 1 + 1. Therefore, $f (2) = 2$ f(2) = 2. Similarly, the number $3$ can only be represented as the sum of three ones: $3 = 1 + 1 + 1$ 3 = 1 + 1 + 1. Hence, $f (3) = 3$ f(3) = 3.

The number $4$ can be written either as the sum of four ones: $4 = 1 + 1 + 1 + 1$ 4 = 1 + 1 + 1 + 1, or as a product: $4 = (1 + 1) \cdot (1 + 1)$ 4 = (1 + 1) \cdot (1 + 1). However, both representations use $4$ ones, so $f (4) = 4$ f(4) = 4.

Now consider an expression whose value is $n$ .

1. Suppose the last operation performed is addition. Let one term be equal to $i$ and consist of $f (i)$ ones, and the other term be equal to $n - i$ n - i and consist of $f (n - i)$ f(n - i) ones. Then the value of $i$ should be chosen so that the sum $f (i) + f (n - i)$ f(i) + f(n - i) is minimized.

At the same time, it is sufficient to iterate the value of $i$ up to $n /2$ , since we can assume that the first summand does not exceed the second. Thus, we obtain the following relation:

f (n) = 1 \leq i \leq n /2 min (f (i) + f (n - i))

f(n) = \min_{1 \le i \le n/2} (f(i)+f(n - i))

2. Suppose the last operation performed was multiplication. Assume that the first factor $i$ consists of $f (i)$ ones, and the second factor $n / i$ consists of $f (n / i)$ ones. This case occurs when $n$ is divisible by $i$ without remainder.

We should choose the value of $i$ such that the sum $f (i) + f (n / i)$ f(i) + f(n / i) is minimized. At the same time, it is sufficient to iterate over $i$ in the range from $2$ to $⌊ n ⌋$ \lfloor \sqrt{n} \rfloor. Thus, we obtain the following relation:

f (n) = 1 \leq i \leq n min (f (i) + f (n / i))

f(n) = \min_{1 \le i \le \sqrt{n}} (f(i)+f(n/i))

Therefore,

f (n) = min (1 \leq i \leq n /2 min (f (i) + f (n - i)), 1 \leq i \leq n min (f (i) + f (n / i)))

f(n) = \min\left( \min_{1 \le i \le n/2} \bigl(f(i) + f(n - i)\bigr),\; \min_{1 \le i \le \sqrt{n}} \bigl(f(i) + f(n / i)\bigr) \right)

Example

Сompute the answer for $n = 7$ n = 7:

f (7) = f (6) + f (1) = (f (2) + f (3)) + f (1) = 2 + 3 + 1 = 6

f(7) = f(6) + f(1) = (f(2) + f(3)) + f(1) = 2 + 3 + 1 = 6

Thus, the number $7$ can be represented using $6$ ones, namely:

7 = (1 + 1) \cdot (1 + 1 + 1) + 1

7 = (1 + 1) \cdot (1 + 1 + 1) + 1

Algorithm implementation

Declare an array $r es$ .

int res[5001];

Read the input value $n$ .

scanf("%d",&n);

Initialize $r es [1] = 1$ res[1] = 1.

res[1] = 1;

Next, compute the values $r es [2], r es [3], ..., r es [n]$ res[2], res[3], ..., res[n] sequentially using the formula given above.

for (i = 2; i <= n; i++)
{
  res[i] = i;
  for (j = 1; 2 * j < i; j++)
    if (res[j] + res[i - j] < res[i]) res[i] = res[j] + res[i - j];
  for (j = 2; j * j <= i; j++)
    if (i % j == 0) 
      if (res[j] + res[i / j] < res[i]) res[i] = res[j] + res[i / j];
}

C++

Print the answer.

printf("%d\n",res[n]);