Calculate mode of a sequence of numbers without using arrays/vectors

Question

I'm a TA for an Introduction to MATLAB course, and the class has not yet learned the use of arrays (or in MATLAB, vectors). There is an exam coming up and one of the questions on the study guide is as follows:

[Tough problem] A mode is the number in a sequence that appears the most number of times. A user is prompted to enter a sequence of non-negative numbers in non-decreasing order one-by-one. The user indicates the end of the sequence by entering a negative number. Write a script to obtain such user input and determine the mode of the sequence. If there are multiple modes, you may report any one of them as the mode. Do not use arrays. Below is an example run:

Determine mode of a set of nonnegative integers.
Use a negative number to quit.
Give me a number:  70
Another number not smaller than the previous: 71
Another number not smaller than the previous: 80
Another number not smaller than the previous: 80
Another number not smaller than the previous: 80
Another number not smaller than the previous: 91
Another number not smaller than the previous: 93
Another number not smaller than the previous: -1
  Mode is 80.

I've been thinking about it, but I can't come up with a good solution. Does anyone know if there is a good way to solve this?

The only solutions I can come up with are ugly hacks that attempt to simulate the use of an array by other means, such as using a string with delimiters to simulate a dictionary-like object.

Answer 1

The key point here is "Another number not smaller than the previous:". That means the input sequence is always sorted, and if there are equal numbers they must appear next to each other. Assume only 1 mode is needed, it should be trivial to deduce it using the variables current_mode_so_far, frequency_of_current_mode, input and frequency_of_input.

Answer 2

Clue: Since the input sequence is in non-decreasing order, you know that (in your example) once you have seen a number greater than 80, you are never going to see an 80 again. So at that point you know exactly how many 80s are in the sequence.

Perhaps you could remember that number and clue ends here

Answer 3

You don't really need to store the whole values (i.e. array or vector).

Since the elements come in monotonic fashion, you just keep the mode seen so far (and how many times it has appeared). If a new element overtakes the current mode, just replace it and the count.

Answer 4

Something like this might work:

num = input('Give me a number: ');
mode = num;
prev = num;
n = 1;
bestn = -1;

while num > 0
    num = input('Another number not smaller than the previous: ');
    if num > prev
        %New number
        if n > bestn
            %New mode
            bestn = n;
            mode = prev;
        end
        n = 1;
    else
        n = n +1;
    end
    prev = num;
end

fprintf('Mode is %d',mode);