Telephone Numbers – CodinGame solution in C
Telephone Numbers asks how many digit nodes are needed to store all the numbers in a prefix tree, where numbers that share a prefix share the same nodes. Insert each number into a trie digit by digit, creating a child only when it does not exist yet, and count every node you create; that count is the answer.
The problem
A phone company wants to store a list of N telephone numbers in a tree structure where each node holds one digit and numbers starting with the same digits reuse the same branch. Given the list, print how many nodes (digits) the structure contains, not counting an empty root.
Numbers are strings of digits of varying length, they can be prefixes of each other (e.g. 0412 and 041), and the list can contain a few thousand of them, each up to around twenty digits long.
Approach, step by step
- Use an empty rootCreate a root node that holds no digit. Every telephone number becomes a path starting from this root, and the root itself is never counted.
- Walk and createFor each digit of a number, look for a child of the current node carrying that digit. If it does not exist, create it and increment the counter; then move to that child, whether it was just created or already present.
- Index children by digitSince there are only ten possible digits, a fixed array of ten child pointers indexed by digit gives O(1) lookups. In higher-level languages a nested dictionary does the same job in a few lines.
- Print the counterAfter all insertions, the counter equals the number of distinct prefixes of all numbers, which is exactly the number of nodes in the trie.
Complexity
O(total digits)O(total digits)Each digit of each number triggers one child lookup and at most one node creation. In the worst case, with no shared prefixes, the trie holds one node per input digit.
Solution code
Telephone Numbers – C
The C code reads each number with getchar() until the newline, and stores up to ten children per node in an array scanned linearly, which is fine for at most ten entries. freeItem is declared but only the root is freed; the process ends right after, so this has no effect on the result.
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
struct item {
int digit;
int nbChildren;
struct item* children[10];
};
// Returns a new item which has the digit 'd'
struct item *newItem(int d)
{
struct item *it = malloc(sizeof(*it));
it->digit = d;
it->nbChildren = 0;
return it;
}
// If it exits, returns a pointer toward the child of item 'f'
// which has the digit 'digit', else returns NULL
struct item *getChild(struct item *f, int d)
{
for (int i = 0; i < f->nbChildren ;i++)
if (f->children[i]->digit == d)
return f->children[i];
return NULL;
}
// Add a child which has the digit 'digit' to item 'father'
void addChild(struct item *f, int d)
{
struct item *child = newItem(d);
f->children[f->nbChildren] = child;
f->nbChildren++;
}
// Frees an item and its children recursively
void freeItem(struct item *it)
{
for (int i = 0; i < it->nbChildren; i++)
free(it->children[i]);
free(it);
}
int main(int argc, char **argv)
{
int N;
scanf("%d\n", &N);
int result = 0;
struct item *root = newItem(-1);
for (int i = 0; i < N; i++) {
int c;
struct item *current = root;
/* Reads through the telephone number, moving along the corresponding
branches of the tree and adding nodes if needed*/
while ((c = getchar()) != '\n' && c != EOF) {
if (getChild(current, c-'0') == NULL) {
addChild(current, c-'0');
result++;
}
current = getChild(current, c-'0');
}
}
free(root);
printf("%d\n", result);
return EXIT_SUCCESS;
}
Common mistakes
- Counting characters instead of new nodesSumming the lengths of all numbers overcounts as soon as two numbers share a prefix. Only increment when you actually create a node.
- Treating a prefix number as a new branchIf 0467 is already stored, adding 046 creates zero new nodes, because every one of its digits already exists. Solutions that mark 'end of number' and add a node for it give a wrong count.
- Reading numbers as integersParsing numbers with int or %d drops leading zeros, and many numbers start with 0. Read each one as a string.
- Line ending handling in CWhen reading character by character, stop on '\n' and on EOF, since the last line may not end with a newline. Forgetting EOF leads to an infinite loop or garbage on the final test.
Going further
You do not even need an explicit tree: the number of trie nodes is exactly the number of distinct non-empty prefixes among all numbers. So in Python, len({num[:i] for num in numbers for i in range(1, len(num)+1)}) is a complete, correct solution. It costs O(total digits × average length) because of the slices, which is fine for this puzzle's sizes, and it makes a good sanity check against your trie version. Thinking in terms of prefixes also explains why insertion order does not matter: a set of prefixes is the same whichever number you add first.
FAQ
Is the answer the number of trie nodes or edges?
Both give the same value here, since every non-root node has exactly one incoming edge. Count the nodes you create, excluding the root.
What if the same number appears twice?
The second insertion walks an existing path and creates no node, so duplicates do not change the result.
Do I need a PATRICIA (compressed) trie?
No. The puzzle counts one node per digit, which corresponds to a plain trie. Compressing branches would change the count.