A. Nastya and an Array

Codeforces

IDCF992A

Time1000ms

Memory256MB

Difficulty—

implementationsortings

English · Original

Chinese · Translation

Formal · Original

Nastya owns too many arrays now, so she wants to delete the least important of them. However, she discovered that this array is magic! Nastya now knows that the array has the following properties: * In one second we can add an arbitrary (possibly negative) integer to all elements of the array that are not equal to zero. * When all elements of the array become equal to zero, the array explodes. Nastya is always busy, so she wants to explode the array as fast as possible. Compute the minimum time in which the array can be exploded. ## Input The first line contains a single integer _n_ (1 ≤ _n_ ≤ 105) — the size of the array. The second line contains _n_ integers _a_1, _a_2, ..., _a__n_ ( - 105 ≤ _a__i_ ≤ 105) — the elements of the array. ## Output Print a single integer — the minimum number of seconds needed to make all elements of the array equal to zero. [samples] ## Note In the first example you can add - 1 to all non-zero elements in one second and make them equal to zero. In the second example you can add - 2 on the first second, then the array becomes equal to \[0, 0, - 3\]. On the second second you can add 3 to the third (the only non-zero) element.

Nastya 拥有太多数组了，因此她希望删除其中最不重要的一个。然而，她发现这个数组是神奇的！Nastya 现在知道该数组具有以下性质： Nastya 总是很忙，因此她希望尽可能快地使数组“爆炸”。请计算使数组爆炸所需的最少时间。第一行包含一个整数 $n$ ($1 ≤ n ≤ 10^5$) —— 数组的大小。第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$ ($ - 10^5 ≤ a_i ≤ 10^5$) —— 数组的元素。请输出一个整数 —— 使数组中所有元素变为零所需的最少秒数。在第一个例子中，你可以在一秒钟内将 $-1$ 加到所有非零元素上，使它们变为零。在第二个例子中，你可以在第一秒添加 $-2$，此时数组变为 $[0, 0, - 3]$。在第二秒，你可以将 $3$ 加到第三个（唯一非零）元素上。 ## Input 第一行包含一个整数 $n$ ($1 ≤ n ≤ 10^5$) —— 数组的大小。第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$ ($ - 10^5 ≤ a_i ≤ 10^5$) —— 数组的元素。 ## Output 请输出一个整数 —— 使数组中所有元素变为零所需的最少秒数。 [samples] ## Note 在第一个例子中，你可以在一秒钟内将 $-1$ 加到所有非零元素上，使它们变为零。在第二个例子中，你可以在第一秒添加 $-2$，此时数组变为 $[0, 0, - 3]$。在第二秒，你可以将 $3$ 加到第三个（唯一非零）元素上。

Given an array $ a = [a_1, a_2, \dots, a_n] $ of integers, define an operation as adding any real number $ x $ to all non-zero elements of the array in one second. The goal is to make all elements equal to zero in the minimum number of operations. Let $ S = \{ a_i \mid a_i \ne 0 \} $ be the set of non-zero elements. Let $ T $ be the set of distinct non-zero values in $ a $. **Objective:** Minimize the number of operations required to reduce all elements to zero, where in each operation, a single value $ x $ can be added to all current non-zero elements. **Key Insight:** Each operation can eliminate one distinct non-zero value (by adding its negation), but only if all occurrences of that value are simultaneously targeted. Since adding the same $ x $ to all non-zero elements affects all distinct non-zero values simultaneously, the problem reduces to: How many distinct non-zero values must be eliminated? Each operation can eliminate at most one distinct non-zero value (by choosing $ x = -v $ for some $ v \in T $), and after that, $ v $ becomes zero and is no longer affected in future operations. Thus, the minimum number of operations equals the number of distinct non-zero elements in the array. **Formal Statement:** Let $ a \in \mathbb{Z}^n $, with $ n \geq 1 $, and $ a_i \in [-10^5, 10^5] $. Define: $$ T = \{ a_i \mid a_i \ne 0 \} $$ Then the minimum number of operations required is: $$ |T| $$ **Answer:** $$ \boxed{|T|} $$

Samples

Input #1

5
1 1 1 1 1

Output #1

Input #2

3
2 0 -1

Output #2

Input #3

4
5 -6 -5 1

Output #3

API Response (JSON)

{
  "problem": {
    "name": "A. Nastya and an Array",
    "description": {
      "content": "Nastya owns too many arrays now, so she wants to delete the least important of them. However, she discovered that this array is magic! Nastya now knows that the array has the following properties: * ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF992A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Nastya owns too many arrays now, so she wants to delete the least important of them. However, she discovered that this array is magic! Nastya now knows that the array has the following properties:\n\n* ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Nastya 拥有太多数组了，因此她希望删除其中最不重要的一个。然而，她发现这个数组是神奇的！Nastya 现在知道该数组具有以下性质：\n\nNastya 总是很忙，因此她希望尽可能快地使数组“爆炸”。请计算使数组爆炸所需的最少时间。\n\n第一行包含一个整数 $n$ ($1 ≤ n ≤ 10^5$) —— 数组的大小。\n\n第二行包含 $n$ 个整数 $a_1, a_2, ..., a_n$ ($ - ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Given an array $ a = [a_1, a_2, \\dots, a_n] $ of integers, define an operation as adding any real number $ x $ to all non-zero elements of the array in one second. The goal is to make all elements equ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments