Java - counting most common elements

Question

The task is to write a code which counts the most common number. For example A[1,2,4,4,4,5,6,7,4] would be 4 with 4 counts. I need to keep this code simple because I just tried to implement my code from algorithm and data structure to java.

My idea was this but somehow I never reach the last condition.

public class countingNumbers{

     public static void main(String []args){
         System.out.print(counting(new int[]{1,1,1,2,3,4,4,4,4,5,6}));
     }

     public static int counting(int[] x){
         int memory = 0; 
         int counter = 0;
         int mostCommon = 0;
         for(int i = 0; i < x.length-1;i++){
             for(int j = i+1; j < x.length-1; j++){
                 if(x[i] == x[j]){
                     counter = counter +1;

                 }
                 else if(j == x.length-1 && counter >= memory){
                     mostCommon = x[i];
                     memory = counter;
                     counter = 0;


                 }
             }
         }
         return  mostCommon;
     }
}

-> Thanks in advance for all your answers, I appreciate that. I'am just looking for the logic not for stream, api's or whatever. I tried do handwrite the code and the implementation in java is only for myself to see if it worked out but unfortunately it doesn't.

Update - the right Solution is this:

public class countingNumbers{

 public static void main(String []args){
     System.out.print(counting(new int[]{1,2,2,2,6,2}));
 }

 public static int counting(int[] x){
     int memory = 0; 
     int counter = 1;
     int mostCommon = 0;
     for(int i = 0; i < x.length;i++){
         for(int j = i+1; j <= x.length-1; j++){
             if(x[i] == x[j]){
                 counter = counter + 1;

             }
             if(j == x.length-1 && counter >= memory){
                 mostCommon = x[i];
                 memory = counter;
                 counter = 1;


             }
         }counter = 1;
     } return memory;


 }

}

Answer 1

I'd stream the array and collect it in to a map the counts the occurrences of each element, and then just return the one with the highest count:

/**
 * @return the element that appears most in the array.
 * If two or more elements appear the same number of times, one of them is returned.
 * @throws IllegalArgumentException If the array is empty
 */
public static int counting(int[] x){
    return Arrays.stream(x)
                 .boxed()
                 .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()))
                 .entrySet()
                 .stream()
                 .max(Map.Entry.comparingByValue())
                 .map(Map.Entry::getKey)
                 .orElseThrow(() -> new IllegalArgumentException("x must not be empty"));
}

Answer 2

If you are good with stream api.. or just for educational goals there is stream solution with groupingBy:

Integer[] arr = {1, 1, 1, 2, 3, 4, 4, 4, 4, 5, 6};

Map<Integer, Long> map = Arrays.stream(arr)
        .collect(Collectors.groupingBy(o -> o, Collectors.counting()));

Integer common = map.entrySet().stream()
        .max(Comparator.comparingLong(Map.Entry::getValue))
        .map(Map.Entry::getKey).get();

System.out.println(common);

Update: If stream is not relevant for you:

It can be done by foor-loop but still it's quite convenient to use Map here:

public static int counting(int[] x) {
    Map<Integer, Long> map = new HashMap<>(); // key is a number, value is how often does it appear in the array 
    for (int number : x) {
        if (map.get(number) != null) {
            map.put(number, map.get(number) + 1);
        } else {
            map.put(number, 1L);
        }
    }
    return Collections.max(map.entrySet(), Map.Entry.comparingByKey()).getKey();
}

Note: there are many ways to get key from map associated with max value. See here to find the most suitable way: Finding Key associated with max Value in a Java Map

Also if else statement can be replaced by merge method from java8:

map.merge(number, 1L, (a, b) -> a + b);

Answer 3

Take a look at these two lines:

 for (int j = i + 1; j < x.length - 1; j++) {

and

} else if (j == x.length - 1 && counter >= memory)

You loop while j is strictly less than x.length - 1, but your else if only triggers when j is exactly equal to x.length - 1. So you can never hit the code in your else if block.

Also, your counter should really start at one, since you're counting the number of entries that match the one you're looking at, so you skip counting the first one. But since you're not outputting the counter anywhere, it's not terribly relevant I guess.

So to fix your code, change your inner for loop to go to j <= x.length - 1.

Answer 4

Declare two variables to hold the most common number and its frequency:

int mostCommon =Integer.MIN_VALUE;

int highFreq = 0;

Itereate over your array. For each element iterate over your array again and count its frequency. If current count is greater than highFreq update mostCommon by seting it to current element and set highFreq current count. Example:

public class countingNumbers{

    public static void main(String[] args) {
        int[] res = counting(new int[]{6, 4, 5, 4, 5, 6, 4, 3, 2});
        System.out.println("most common number is: " + res[0] + " with " + res[1] + " counts");
    }

    public static int[] counting(int[] x) {
        int mostCommon = Integer.MIN_VALUE;
        int highFreq = 0;
        for (int i = 0; i < x.length; i++) {
            int currFreq = 0;
            for (int j = 0; j < x.length; j++) {
                if (x[i] == x[j]) {
                    currFreq++;
                }
            }
            if (highFreq < currFreq) {
                highFreq = currFreq;
                mostCommon = x[i];
            }
        }
        return new int[]{mostCommon, highFreq};
    }
}