# CHEFPDIG - Editorial

[Practice][111]

[Contest][222]

Author: [Dmytro Berezin][4444]

Tester: [Jingbo Shang][5555]

Editorialist: [Hanlin Ren][6666]

Simple

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 A-Z can \overline{ab}(i.e., 10a+b) be its ASCII code?

### 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:

language Define a string Read a string
C  char s[MAXLEN+10];   scanf("%s", s); 
C++  #include string s;   cin >> s; 
Python 
</td><td>


s = raw_input();

</td></tr>
</table>

## 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 char is just a signed 8-bit integer, so we don't need to convert anything. For example, we can enumerate the ASCII codes of all capital letters like this:



for (char c = ‘A’; c <= ‘Z’; c++)
do something


Also if we want the first(or last) digit of the ASCII code of a character(say 'A'), we just treat it as an integer:



asc = ‘A’;
first_dgt = asc / 10;
last_dgt = asc % 10;


Some other language may have functions converting between ASCII codes and characters. For example, Python provides two functions ord(char) and chr(ascii code). You can also google to find out how to do this in your language.

## The solution

Let's consider every character $c$ from 'A' to 'Z' separately. Suppose $c$ has ASCII code $\overline{ab}$. Let the input be $s$(a string).

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 s[i] to recognize the end of string, since C-style string ends with ASCII 0.(a common mistake is that don't confuse s[i] != 0 with s[i] != '0'. 0 is NULL character but '0' has ASCII $48$)



count = 0;
for (int i = 0; s[i] != 0; i++)
if (s[i] == c) count++;


In C++, you can use string::length() method to get a string's length:



count = 0;
for (int i = 0; i < s.length(); i++)
if (s[i] == c) count++;


In some languages like Python, things become even easier! Just use s.count(ch) to count how many times a char $ch$ appears in a string $s$.

The time complexity is $O(\sigma|s|)$, where $|s|$ is the length of input, and $\sigma=26$ is the size of alphabet.

## A common mistake
If you use C/C++, you may write the following code:



for (int i = 0; i < strlen(s); i++)
do something;


This code may make you TLE. Why? Because strlen()'s time complexity is $O(len)$, not $O(1)$. The code above executes $O(|s|)$ strlen()'s, and each execution takes $O(|s|)$ time, so the time complexity is actually $O(|s|^2)$.

A small modification should correct this mistake:



int l = strlen(s);
for (int i = 0; i < l; i++)
do something;


However, in C++, if s is a string(rather than a char array), the following code is OK:



for (int i = 0; i < s.length(); i++)
do something;


This is because length() method is $O(1)$.

### 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$.



for (int i = 0; s[i]; i++)
occur[s[i] - ‘0’]++;


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][444].
Editorialist's solution can be found [here][555].

[111]: http://www.codechef.com/problems/CHEFPDIG
[222]: http://www.codechef.com/SEPT17/problems/CHEFPDIG

[4444]: http://www.codechef.com/users/berezin
[555]: http://www.codechef.com/download/Solutions/SEPT17/Editorialist/CHEFPDIG.py`