PROBLEM LINK:Author: Dmytro Berezin Tester: Jingbo Shang Editorialist: Hanlin Ren DIFFICULTY:Simple PREREQUISITES:None PROBLEM:Given a number $s$(actually a string of digits), pick two digits $a,b$ in $s$ that's different by position. For which characters between EXPLANATION:How to store that big number?This is the most frequent comment we receive. The number $N$ can be as large as $10^{100\ 000}$, so we can only store this number as a string. That is, we regard the input as a string of length $100\ 000$. Here are some code snippets to manipulate a string:
How do I handle ASCII codes?Also we need to convert between a character and its ASCII code. This is easy in C/C++: a
Also if we want the first(or last) digit of the ASCII code of a character(say
Some other language may have functions converting between ASCII codes and characters. For example, Python provides two functions The solutionLet's consider every character $c$ from When $a\ne b$, we need to pick both $a$ and $b$ from $s$. We can just check if both digit appears in $s$. When $a=b$, we need to pick two $a$'s from $s$, thus we need to check if $a$ appears in $s$ twice. We need to find how many time a character occurs in $s$. This can be done by iterating all chars in $s$. In C you can use
In C++, you can use
In some languages like Python, things become even easier! Just use The time complexity is $O(\sigmas)$, where $s$ is the length of input, and $\sigma=26$ is the size of alphabet. A common mistakeIf you use C/C++, you may write the following code:
This code may make you TLE. Why? Because A small modification should correct this mistake:
However, in C++, if
This is because ALTERNATIVE SOLUTION:We first preprocess $s$, and maintain a table $occur[0\sim 9]$, where $occur[i]$ is the number of times that digit $i$ appears in $s$.
Let's then do the algorithm above. Suppose the ASCII code we are checking is $\overline{ab}$. When $a\ne b$, we check if $occur[a]\ge 1$ and $occur[b]\ge 1$. When $a=b$, we check if $occur[a]\ge 2$. The time complexity is $O(s)$. AUTHOR'S AND TESTER'S SOLUTIONS:Tester's solution can be found here.
This question is marked "community wiki".
asked 16 Aug '17, 21:21
