Loading page…
Practice problem · medium
An ad platform imports audience ids from a spreadsheet. The spreadsheet wrote every id as a decimal number, so the same id can arrive as 7, 7.0 or 07.
A teammate parsed each id into a floating-point number and used it as a table key. Some different ids were merged, and some equal ids were kept apart. Your team lead says: "Count the different ids, by numeric value, and do not lose or invent any."
Write distinct_ids(ids).
-, one or more digits, and optionally a . followed by one or more digits. It has at most 40 characters.7, 07 and 7.0 are one id, and 7.500 is the same id as 7.5. Zero has no sign: -0 and 0.00 are the same id.Input: ids = ["7", "7.0", "07", "7.50", "7.5", "-3.25"]
Output: 3The trace writes each id in one canonical form.
| Step | Id | Canonical form | New? |
|---|---|---|---|
| 1 | 7 |
7. |
yes |
| 2 | 7.0 |
7. |
no |
| 3 | 07 |
7. |
no |
| 4 | 7.50 |
7.5 |
yes |
| 5 | 7.5 |
7.5 |
no |
| 6 | -3.25 |
-3.25 |
yes |
Input: ids = ["0", "-0", "0.00", "-0.0"]
Output: 1Every id is zero.
Input: ids = ["0.1", "0.10000000000000000555", "0.1000"]
Output: 2The second id is a little larger than 0.1, so it is a different number. A double rounds both to the same value.
1 ≤ ids.length ≤ 20,000. and -, in the form above.Comparing each id with every different earlier id costs up to n × n / 2 = 2 × 10^8 comparisons, and each comparison works on up to 40 characters. That is too slow for the limit.
The ids are text, up to 40 characters, so a double cannot hold them exactly. A double keeps about 15 to 17 significant digits.
distinct_ids · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.