Solution

Full source code is available here.

The immediate solution that comes to mind is to iterate the notes array, count how many times each note occurs and return the number of notes that occurs only once.

You can do this with LINQ very easily.

It’s easy to forget how much concise the code becomes using LINQ. This is the equivalent version using imperative statements.

This code is perfectly valid and quick enough to pass all system tests. The size of the array is always less then 50 and there is no need to optimize it during a competition.

What if there was no constraint in the array size?

The previous algorithm has two nested loop then is complexity is O(N^2). It does not scale with the size of the input. It is too inefficient.

We can change the algorithm to make it linear in time using a Dictionary to keep track of the occurrences of each note. The only price to pay is a bit of overhead in terms of memory requirements for the dictionary.

Personal Notes

This problem was very easy and I didn’t have any problem in solving it. There is only an interesting observation to make about the first LINQ implementation. If the problem asked to count the number of notes that occur exactly twice in the given song just replacing 1 with 2 would not work. The reason is that we do the count for each note in the array and that includes duplicates. The original code work only because if the note appears only once in the array we will never encounter a duplicate later in the processing. Something to keep in mind when you use a similar LINQ approach in the future.