Thread: Mode of an array (with restricted command terms)

  1. #1
    Registered User
    Join Date
    Oct 2015
    Posts
    1

    Lightbulb Mode of an array (with restricted command terms)

    Hey all!
    I am writing a code in C to find the mode of an array of numbers. I understand that this has been solved before but I am only allowed to use certain command terms in my program.
    I am allowed to use loops, if and while statements, flags.
    If I understand it correctly I need one loop that compares each term in the array to the other terms and stores how many times each number appears in each array.
    So:
    Input: A list of numbers (non integers too)
    Output: the mode of the list of numbers. (If two numbers appear the same amount of times display no mode)

    I already have the typing in of the numbers done, so I need the loop to check the array for how many times each number appears, store that in another array. Another loop to check the last array to see which number if the biggest and what it corresponds to.

    Thank you so much!

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,677
    Sounds like you know what to do.
    We look forward to seeing your attempt when you get stuck.
    Announcements - C Programming
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,782
    Surely that cannot be the whole/correct task description. I assume that since you're asking the question that you're new to programming and based on that I conclude that either your instructor is insane (this is not a trivial exercise, especially since it involves "non-integers"), or that you've described the task required incorrectly.

  4. #4
    Registered User
    Join Date
    May 2009
    Posts
    4,181
    Real world warning: Comparing floating point number for being equal tends to be something that is NOT a good idea unless you know what tolerance/range should count as being equal.

    Other that that the problem does NOT look to hard to me.
    I would create a second array that contains the value and number of times it existed in the list.
    (This method ignores the real word problem; I stated already.)

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  5. #5
    Ticked and off
    Join Date
    Oct 2011
    Location
    La-la land
    Posts
    1,728
    Quote Originally Posted by stahta01 View Post
    I would create a second array that contains the value and number of times it existed in the list.
    I wouldn't, unless you need the entire histogram of unique values.

    If you do need the histogram, then using it does make a lot of sense, though. Just make each histogram bin represent an unique value, and mode is the bin with the highest count. You can do this in linear time, too.

    If you want to find minimum, maximum, and median, it is easier to just sort the values first. Then, the first element in the array is the minimum, the last element in the array is the maximum, the middle element in the array is the median (which is very useful in e.g. benchmarking). You can find out the average=mean (by summing all the values and dividing by the count), and the mode, using a single linear pass over the array.

    The logic for finding the mode in a sorted array is simple, and can be done in linear time. In pseudocode:
    Code:
        best_multiple := false
        best_value := array[0]
        best_count := 1
    
        if length < 2
            return best_value (only value in the array)
    
        curr_value := best_value
        curr_count := best_count
    
        for index := 1 .. length-1
    
            if array[index] == curr_value
                curr_count = curr_count + 1
            else
                if curr_count > best_count
                    best_value = curr_value
                    best_count = curr_count
                    best_multiple = false
                else
                if curr_count == best_count
                    best_multiple = true
    
                curr_value = array[index]
                curr_count = 1
    
        if curr_count > best_count
            best_value = curr_value
            best_count = curr_count
        else
        if curr_count = best_count
            best_multiple = true
    
        if best_multiple
            return nothing (more than one mode)
        else
            return best_value (occurs best_count times)
    Without sorting the array, you do need a double loop to find the mode. In pseudocode:
    Code:
        if length < 1
            return nothing (empty array)
        if length < 2
            return array[0] (only one item in the array)
        if length < 3
            return nothing (two values in array, both modes)
    
        best_multiple = false
        best_value = 0
        best_count = 0
    
        for i = 0 .. length-1
            count = 0
    
            value = array[i]
    
            for k = 0 .. length-1
                if array[k] == value
                    count = count + 1
    
            if count > best_count
                best_count = count
                best_value = array[i]
                best_multiple = false
            else
            if count == best_count
                best_multiple = true
    
        if best_multiple == true
            return nothing (because multiple modes)
        else
            return best_value (which occurs best_count times)
    In the latter case, it is easy to either limit comparison to specific number of decimal digits (by multiplying with a suitable power of ten, then rounding, before comparison), or to consider all numbers that differ from the central value by at most epsilon as equal to value.

    To limit to specific number of digits, use value = round(poweroften * array[i]) and if (value == round(poweroften * array[k])) , where poweroften is a suitable power of ten; 101=10 if you want one decimal digit, 102=100 if two, 103=1000 if three, and so on. (You can use pow(10, digits) from <math.h> to calculate poweroften.)

    To look for values that differ by not more than epsilon, use value = array[i] as in the original two-nested-loops pseudocode above, but test using if (value - epsilon <= array[k] && array[k] <= value + epsilon).
    This is basically a search for the largest group of similar values, where we try to find the value in the array that has the most neighbours within distance epsilon.
    If for example the values in the array are known to have ±epsilon of random noise, this too is mode. This is really, really useful if the values are real-world measurements, and you need their mode!
    Note that even if the data is sorted, a double loop is needed in this case.

    I hope you don't mind me butting in, stahta01.

    In general, I too recommend the histogram approach, because a histogram tells one much more about a distribution than just minimum, maximum, median, and mode. It's just that to calculate those four values, you don't need it, really. And for finding the mode in noisy data, the histogram approach does not really work (because the bin boundaries are exact).

    To the OP: I deliberately provided you with much, much more information than you actually need. This, to me, serves two purposes: First, it shows others looking at problems involving finding the mode some real-world useful options. Second, while the post contains basically all information to solve the problem statement outlined in the first post, it is not copy-pastable: you need to read and think until you understand and can apply that understanding -- learn -- to make use of it. I consider this a win-win-I'mTooVerbose situation.

  6. #6
    Registered User
    Join Date
    May 2009
    Posts
    4,181
    Quote Originally Posted by Nominal Animal View Post
    I hope you don't mind me butting in, stahta01.
    Does NOT bother me at all.
    I was just guessing the Original Poster (OP) does NOT know how to sort at this point in time.

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  7. #7
    Ticked and off
    Join Date
    Oct 2011
    Location
    La-la land
    Posts
    1,728
    Quote Originally Posted by stahta01 View Post
    Does NOT bother me at all.
    Good! I was butting in, and even if I disagreed, you did have good points in your post.

    Quote Originally Posted by stahta01 View Post
    I was just guessing OP does not know how to sort
    Quite, but I didn't want to just provide the nested-loop-no-sorting solution as pseudocode alone.

    Massaging data is an interesting topic, and I wanted to make sure those trying to find the mode of some data see there are many ways to do it, and perhaps other, better ways to look at and characterize the data they have. You know, "lit the fuse", so to speak, even if nothing sticks for now.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Restricted pointers C99.
    By Mr.Lnx in forum C Programming
    Replies: 7
    Last Post: 07-20-2013, 07:06 PM
  2. Replies: 11
    Last Post: 02-04-2012, 09:46 AM
  3. Setting command mode build in Visual studio
    By Siddu_Kyocera in forum C Programming
    Replies: 1
    Last Post: 05-22-2010, 05:58 AM
  4. Restricted Integer
    By kolucoms6 in forum C++ Programming
    Replies: 6
    Last Post: 03-01-2008, 08:59 PM
  5. How restricted am I by console mode
    By The Gweech in forum C++ Programming
    Replies: 2
    Last Post: 03-20-2002, 09:25 PM

Tags for this Thread