Counting number of pairs in an integer array

Question

So, I wanted to have the count for number of pairs of same integer there are in an array for which I used a HashMap

Input contains two lines:

1. Integer n:

   Signifies the size of input

2. Input numbers separated by white space character:
   E.g 4 6 6 7 7 8 7 6 4

For the same input,

Expected Output:

3

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class SockMerchant {

    public int[] returnsockArr() {
        Scanner sc = new Scanner(System.in);
        int arraySize = sc.nextInt();
        int[] sockArr = new int[arraySize];
        for(int i = 0;i <= arraySize-1; i++) {
            sockArr[i] = sc.nextInt();
        }
        sc.close();
        return sockArr;
    }

    public int returnCount(Map<String, Object> mapCount) {
        int count = 0;
        for(String keyName : mapCount.keySet()) {
            int value = (int)mapCount.get(keyName);
            count = count+(value/2);
        }
        return count;
    }

    public int setMapAndReturnCount(int[] sockArr) {
        Map<String, Object> mapCount = new HashMap<String, Object>();
        for(int j = 0;j<= sockArr.length-1;j++) {
            if(mapCount.containsKey(Integer.toString(sockArr[j]))) {
                mapCount.put(Integer.toString(sockArr[j]), (int)mapCount.get(Integer.toString(sockArr[j]))+1);
            }
            else {
                mapCount.put(Integer.toString(sockArr[j]), 1);
            }
        }
        return returnCount(mapCount);
    }

    public static void main(String args[]) {
        SockMerchant sm = new SockMerchant();
        int[] sockArr = sm.returnsockArr();
        int finalCount = sm.setMapAndReturnCount(sockArr);
        System.out.println(finalCount);
    }
}

I think that I have complicated the solution a bit too much

Is there a better approach to do the same thing?

Answer 1

There are couple of improvement possible in your code.

In this method setMapAndReturnCount you should change the declaration of map from,

Map<String, Object> mapCount = new HashMap<String, Object>();

to

Map<Integer, Integer> mapCount = new HashMap<Integer, Integer>();

As you know, you want to store the input array numbers as key in Map and value is the count of occurence of a particular number in the array.

By using Object class as value in Map, you are defeating one of the main purpose of having generics implementation in Java. If you use Object then you need to uselessly cast, and otherwise don't have to.

Another point in same method, you can write your for loop in a better way like this, instead of your current code which does double work of first checking through containsKey and then uses mapCount.get to again pick the value of key.

public int setMapAndReturnCount(int[] sockArr) {
    Map<Integer, Integer> mapCount = new HashMap<Integer, Integer>();
    for (int j = 0; j < sockArr.length; j++) {
        Integer count = mapCount.get(sockArr[j]);
        if (count == null) {
            mapCount.put(sockArr[j], 1);
        } else {
            mapCount.put(sockArr[j], count + 1);
        }
    }
    return returnCount(mapCount);
}

Similarly, you can change returnCount method to this,

public int returnCount(Map<Integer, Integer> mapCount) {
    int count = 0;
    for (Integer value : mapCount.values()) {
        count += (value / 2);
    }
    return count;
}

As you don't need to first iterate on keySet and then retrieve the values with get which will be slower, and instead just iterate it on values as that is what you need for calculating number of pairs, which will be relatively faster.

Also, if you are using Java-8 and above,

You can change your returnCount to one liner like this,

public int returnCount(Map<Integer, Integer> mapCount) {
    return mapCount.values().stream().mapToInt(x -> x / 2).sum();
}

Answer 2

Separate input handling from the algorithm. E.g. move reading the input from returnsockArr to the main method and change the method to accept an array (of Integers or Strings, the algorithm doesn't really care as long as it receives Comparables). Then you can create test cases by just passing different arrays. Adding the burden of handling input to your algorithm makes it less reusable.

As for the algorithm, sorting the array and processing it once, keeping count of adjacent objects that are equal, would be lot simpler and less error prone.

Answer 3

Naming matters.

int[] sockSizes = {4, 6, 6, 7, 7, 8, 7, 6, 4};
int count = Socks.countPairs(sockSizes);

/**
 * Determine the number of sock pairs one can form.
 * @param sockSizes of single socks available.
 * @return the number of pairs that can be formed.
 */
public static int countPairs(int[] sockSizes) {
    Map<Integer, Integer> sockSizeCounts = new HashMap<>();
    for (int sockSize : sockSizes) {
        sockSizeCounts.merge(sockSize, 1, Integer::sum);
    }
    return sockSizeCounts.values().stream()
        .mapToInt(c -> c / 2)
        .sum();
}

• The problem needs a bit of explanation; javadoc might help; that 4 5 4 6 4 is 1 pair of 4.
• Diamond operator <> saves a bit.
• For-each loop to take elements without the need to introduce an index/iterator.
• Walking over the Map.keySet() and calling get(key), should be done as walking over the Map.entrySet() with getKey() and getValue().
• Map.merge does exactly a frequency count; which needs a bit of explanation; read the javadoc.
• Summing the integer half of all values can be done elegantly by a stream expression; your code is however good style too.

Overall, just a manco on progressive Java constructs.

By the way, a fixed sized array of socks is probably inappropriate in this problem area. List<Integer> socksDrawer = new ArrayList<>(); ;)

---

I just saw that the question is from 2015. No wonder!

Answer 4

I have tried to simplify your code like this.

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class SockMerchant {

    private int[] returnSockArr() {
        Scanner sc = new Scanner(System.in);
        int arraySize = sc.nextInt();
        int[] sockArr = new int[arraySize];
        for(int i = 0;i <= arraySize-1; i++) {
            sockArr[i] = sc.nextInt();
        }
        sc.close();
        return sockArr;
    }

    private int returnCount(int[] sockArr) {
        int count = 0;
        Set<Integer> uniqueElements = new HashSet<>();
        for (int i: sockArr) {
            if(uniqueElements.contains(i)) {
                count ++;
                uniqueElements.remove(i);
            } else {
                uniqueElements.add(i);
            }
        }
        return count;
    }

    public static void main(String args[]) {
        SockMerchant sm = new SockMerchant();
        int[] sockArr = sm.returnsockArr();
        int finalCount = sm.returnCount(sockArr);
        System.out.println(finalCount);
    }
}

I have used your returnSockArr as it is for reading the numbers. Then I have removed setMapAndReturnCount method which uses Map for storing numbers. Instead I am calling returnCount and calculate the number of pairs.

In that method I am putting the number in to a Set if the number is not present in the 'Set'. If number is present the count is incremented and that number is removed from the Set. So count won't be incremented when a number is seen odd times in the list.

And am sure it can be again simplified :)