Finding multiple modes in an array of integers with 1000 elements

Question

So I need a way to find the mode(s) in an array of 1000 elements, with each element generated randomly using math.Random() from 0-300.

int[] nums = new int[1000];

    for(int counter = 0; counter < nums.length; counter++)
        nums[counter] = (int)(Math.random()*300);

int maxKey = 0;
    int maxCounts = 0;

    sortData(array);
    int[] counts = new int[301];

    for (int i = 0; i < array.length; i++)
    {
        counts[array[i]]++;
        if (maxCounts < counts[array[i]]) 
        {
            maxCounts = counts[array[i]];
            maxKey = array[i];
        }
    }

This is my current method, and it gives me the most occurring number, but if it turns out that something else occurred the same amount of times, it only outputs one number and ignore the rest.

WE ARE NOT ALLOWED TO USE ARRAYLIST or HASHMAP (teacher forbade it)

Please help me on how I can modify this code to generate an output of array that contains all the modes in the random array.

Thank you guys!

EDIT:

Thanks to you guys, I got it:

private static String calcMode(int[] array)
{
    int[] counts = new int[array.length];
    for (int i = 0; i < array.length; i++) {
        counts[array[i]]++;
    }
    int max = counts[0];
    for (int counter = 1; counter < counts.length; counter++) {
        if (counts[counter] > max) {
            max = counts[counter];
        }
    }

    int[] modes = new int[array.length];

    int j = 0;
    for (int i = 0; i < counts.length; i++) {
        if (counts[i] == max)
            modes[j++] = array[i];
    }

    toString(modes);
    return "";
}

public static void toString(int[] array)
{
    System.out.print("{");
    for(int element: array)
    {
        if(element > 0)
            System.out.print(element + " ");
    }
    System.out.print("}");
}

A mode is something that occurs the most times in a set. For example, given set {1,1,1,1,1,1,2,3}, 1 would be the mode because it occurs the most amount of times. — user3200640, Jan 16 '14 at 01:41
Hint: You've already computed `maxCounts`; now write a second loop that goes through `counts`. — ajb, Jan 16 '14 at 01:43
@ajb how would that work? Even if I ran a second loop, what about a 3rd mode? 4th? — user3200640, Jan 16 '14 at 01:45
Did the teacher say anything about using the `SET` data structure? A [TreeSet](http://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html) could be used for a concise solution. — , Jan 16 '14 at 01:49
Is `ArrayList` the only `List` you are not allowed to use? There are plenty more implementations like `LinkedList`...; Same holds for `HashMap`. Since I see no reason to insert null as key or value a `Hashtable` should suffice. (Although your teacher will not like that neither, I guess) — fabian, Jan 16 '14 at 01:56
As much as I would love to, I cant. She doesnt want us to use anything except what is in the Array Class — user3200640, Jan 16 '14 at 02:07
@fabian I edited the original Post with some new code, if you could please look at that. — user3200640, Jan 16 '14 at 02:08
@user3200640 You have a `counts` array, and you have `maxCounts`. If `counts[i]` equals `maxCounts`, for any `i`, then you've found a mode. You will be able to find all of them this way. In my opinion you were on the right track with your original code; it looks like your second attempt is just complicating things needlessly. — ajb, Jan 16 '14 at 02:19
@ajb I still dont understand. How can i make it ignore the first mode on the second time through? And the second mode the third time through? — user3200640, Jan 16 '14 at 02:21
@user3200640 Your first loop created an array `counts`, where `counts[1]` is the number of times 1 is in the set, `counts[2]` is the number of times 2 is in the set, etc. So for your example in your comment, it will be `[0,6,1,1,0,0,0,...]`. You've also computed `maxCounts` which will be 6. So now go through `counts` looking for the 6's. Each time you find one, that will be a mode, and then you do something with it, but you don't exit the loop because there might be more 6's. Please think about it. It's really simpler than you seem to be making it. — ajb, Jan 16 '14 at 02:28
@ajb so once I have 'maxCounts', I can make another loop, and traverse 'counts' searching for the same number, then return the value of the subscript as a mode> — user3200640, Jan 16 '14 at 02:31
See this post: [finding-multiple-modes-in-an-array](http://stackoverflow.com/questions/8858327/finding-multiple-modes-in-an-array?rq=1) — , Jan 16 '14 at 02:35
@Christian nailed it before I could use those algorithms to reimplement on the array. — , Jan 16 '14 at 02:43
@Christian Thank you so much, I was able to finish the code. Ive updated the OP with the working answer. — user3200640, Jan 16 '14 at 02:47

score 1 · Answer 1 · answered Jan 16 '14 at 02:38

Your first approach is promising, you can expand it as follows:

for (int i = 0; i < array.length; i++)
{
    counts[array[i]]++;
    if (maxCounts < counts[array[i]]) 
    {
        maxCounts = counts[array[i]];
        maxKey = array[i];
    }
}

// Now counts holds the number of occurrences of any number x in counts[x]
// We want to find all modes: all x such that counts[x] == maxCounts

// First, we have to determine how many modes there are
int nModes = 0;

for (int i = 0; i < counts.length; i++)
{
    // increase nModes if counts[i] == maxCounts
}

// Now we can create an array that has an entry for every mode:
int[] result = new int[nModes];

// And then fill it with all modes, e.g:
int modeCounter = 0;
for (int i = 0; i < counts.length; i++)
{
    // if this is a mode, set result[modeCounter] = i and increase modeCounter  
}

return result;

score 1 · Accepted Answer · answered Jan 16 '14 at 02:38

Look at this, not full tested. But I think it implements what @ajb said:

private static int[] computeModes(int[] array)
{
    int[] counts = new int[array.length];
    for (int i = 0; i < array.length; i++) {
        counts[array[i]]++;
    }
    int max = counts[0];
    for (int counter = 1; counter < counts.length; counter++) {
        if (counts[counter] > max) {
            max = counts[counter];
        }
    }

    int[] modes = new int[array.length];

    int j = 0;
    for (int i = 0; i < counts.length; i++) {
        if (counts[i] == max)
            modes[j++] = array[i];
    }

    return modes;
}

This will return an array int[] with the modes. It will contain a lot of 0s, because the result array (modes[]) has to be initialized with the same length of the array passed. Since it is possible that every element appears just one time.

When calling it at the main method:

public static void main(String args[])
{
    int[] nums = new int[300];

    for (int counter = 0; counter < nums.length; counter++)
        nums[counter] = (int) (Math.random() * 300);

    int[] modes = computeModes(nums);
    for (int i : modes)
        if (i != 0) // Discard 0's
            System.out.println(i);
}

Look the edit, you have to print each element in the array, not the array. — Christian Tapia, Jan 16 '14 at 02:41
Never mind, I just needed to use a custom toString() method, and it worked. I'll update the OP. Thank you! — user3200640, Jan 16 '14 at 02:45

score 0 · Answer 3 · answered Jan 16 '14 at 02:43

THIS USES AN ARRAYLIST but I thought I should answer this question anyways so that maybe you can use my thought process and remove the ArrayList usage yourself. That, and this could help another viewer.

Here's something that I came up with. I don't really have an explanation for it, but I might as well share my progress:

Method to take in an int array, and return that array with no duplicates ints:

public static int[] noDups(int[] myArray) 
{ 
    // create an Integer list for adding the unique numbers to
    List<Integer> list = new ArrayList<Integer>();

    list.add(myArray[0]); // first number in array will always be first
    // number in list (loop starts at second number)

    for (int i = 1; i < myArray.length; i++)
    {
        // if number in array after current number in array is different
        if (myArray[i] != myArray[i - 1]) 
            list.add(myArray[i]); // add it to the list
    }

    int[] returnArr = new int[list.size()]; // create the final return array
    int count = 0;

    for (int x : list) // for every Integer in the list of unique numbers
    {
        returnArr[count] = list.get(count); // add the list value to the array
        count++; // move to the next element in the list and array
    }

    return returnArr; // return the ordered, unique array
}

Method to find the mode:

public static String findMode(int[] intSet)
{
    Arrays.sort(intSet); // needs to be sorted

    int[] noDupSet = noDups(intSet);
    int[] modePositions = new int[noDupSet.length];

    String modes = "modes: no modes."; boolean isMode = false;

    int pos = 0;
    for (int i = 0; i < intSet.length-1; i++)
    {
        if (intSet[i] != intSet[i + 1]) {
            modePositions[pos]++;
            pos++;
        }
        else {
            modePositions[pos]++;
        }
    }
    modePositions[pos]++;

    for (int modeNum = 0; modeNum < modePositions.length; modeNum++)
    {
        if (modePositions[modeNum] > 1 && modePositions[modeNum] != intSet.length)
            isMode = true;
    }

    List<Integer> MODES = new ArrayList<Integer>();

    int maxModePos = 0;
    if (isMode) {
        for (int i = 0; i< modePositions.length;i++)
        {
            if (modePositions[maxModePos] < modePositions[i]) {
                maxModePos = i;
            }
        }

        MODES.add(maxModePos);
        for (int i = 0; i < modePositions.length;i++)
        {
            if (modePositions[i] == modePositions[maxModePos] && i != maxModePos)
                MODES.add(i);
        }

        // THIS LIMITS THERE TO BE ONLY TWO MODES
        // TAKE THIS IF STATEMENT OUT IF YOU WANT MORE         
        if (MODES.size() > 2) {
            modes = "modes: no modes.";
        }
        else {
            modes = "mode(s): ";
            for (int m : MODES)
            {
                modes += noDupSet[m] + ", ";
            }
        }
    }
    return modes.substring(0,modes.length() - 2);
}

Testing the methods:

public static void main(String args[]) 
{
    int[] set = {4, 4, 5, 4, 3, 3, 3};
    int[] set2 = {4, 4, 5, 4, 3, 3};
    System.out.println(findMode(set)); // mode(s): 3, 4
    System.out.println(findMode(set2)); // mode(s): 4
}

trust me, my life would be so much easier if she allowed us to use arrayList. Thank you for the answer. — user3200640, Jan 16 '14 at 02:46

score 0 · Answer 4 · answered Jan 16 '14 at 06:07

There is a logic error in the last part of constructing the modes array. The original code reads modes[j++] = array[i];. Instead, it should be modes[j++] = i. In other words, we need to add that number to the modes whose occurrence count is equal to the maximum occurrence count

Finding multiple modes in an array of integers with 1000 elements

4 Answers4