Robert Eisele
Engineer, Systems Architect and DBA

Codingame: Telephone Numbers

Original Problem

The Goal

By joining the iDroid smartphone development team, you have been given the responsibility of developing the contact manager. Obviously, what you were not told is that there are strong technical constraints for iDroid: the system doesn’t have much memory and the processor is as fast as a Cyrix from the 90s...

In the specifications, there are two points in particular that catch your attention:

1. Intelligent Assistance for entering numbers
The numbers corresponding to the first digits entered will be displayed to the user almost instantly.
 

2. Number storage optimization
First digits which are common to the numbers should not be duplicated in the memory.

Fortunately, the specifications also have this little chart to guide you in the implementation:
 

Fig 1. Structure of data to stock phone numbers on iDroid

Your task is to write a program that displays the number of items (which are numbers) required to store a list of telephone numbers with the structure presented above.

Solution

When we implement this problem as a linked list, the only thing to do is counting the number of nodes created. For each telephone number, we then try to insert into the existing structure and count if another node is necessary. The implementation in JavaScript then looks like this:
function insert(str) {

    var l = L;

    for (var i = 0; i < str.length; i++) {
        var c = str[i];

        if (l[c] !== undefined) {
            C++
            l[c] = {};
        }
        l = l[c];
    }
}

var C = 0;
var L = {};
var N = parseInt(readline());
for (var i = 0; i < N; i++) {
    var telephone = readline();
    insert(telephone);
}

print(C);

« Back to problem overview

All images are copyright to Codingame