Can we solve this Sock Merchant problem in less complexity?

Question

I have solved the hackerrank Sock Merchant problem But I want to reduce the complexity of the code(I am not sure that it is possible or not).

John works at a clothing store. He has a large pile of socks that he must pair by color for sale. Given an array of integers representing the color of each sock, determine how many pairs of socks with matching colors there are.

For example, there are n=7 socks with colors ar= [1,2,1,2,1,3,2]. There is one pair of color 1 and one of color 2. There are three odd socks left, one of each color. The number of pairs is 2.

Function Description

Complete the sockMerchant function in the editor below. It must return an integer representing the number of matching pairs of socks that are available.

sockMerchant has the following parameter(s):

• n: the number of socks in the pile

• ar: the colors of each sock

Input Format

The first line contains an integer n, the number of socks represented in ar. The second line contains n space-separated integers describing the colors ar[i] of the socks in the pile.

Constraints

• 1 <= n <= 100

• 1 <= ar[i] <= 100 where 0 <= i < n

Output Format

Return the total number of matching pairs of socks that John can sell.

Sample Input

9
10 20 20 10 10 30 50 10 20

Sample Output

3

---

My solutions :

package com.hackerrank.test;

public class Solution {
    public static void main(String[] args) {
        //Initialize array
        int[] arr = new int[]{10, 20, 20, 10, 10, 30, 50, 10, 20};
        //Array fr will store frequencies of element


        System.out.println("---------------------------------------");
        System.out.println(" sockMerchant output " + sockMerchant(9, arr));
        System.out.println("---------------------------------------");

    }

    static int sockMerchant(int n, int[] ar) {
        int pairs = 0;
        int frequencyArray[] = new int[ar.length];
        int frequencyTemp = -1;
        for (int i = 0; i < ar.length; i++) {
            int count = 1;
            for (int j = i + 1; j < ar.length; j++) {
                if (ar[i] == ar[j]) {
                    count++;
                    frequencyArray[j] = frequencyTemp;
                }
            }
            if (frequencyArray[i] != frequencyTemp) {
                frequencyArray[i] = count;
            }
        }

        for (int i = 0; i < frequencyArray.length; i++) {
            if (frequencyArray[i] != frequencyTemp) {
                int divide = frequencyArray[i] / 2;
                pairs += divide;
            }
        }
        return pairs;
    }
}

And the output is :

    ---------------------------------------
    sockMerchant frequency 3
    ---------------------------------------

Answer 1

You can solve this in a single pass (O(n)) using a HashSet, which has O(1) put and lookup time. Each element is already in the set, in which case it gets removed and the pair counter is incremented, or it's not, in which case you add it:

int[] arr = new int[]{10, 20, 20, 10, 10, 30, 50, 10, 20};

HashSet<Integer> unmatched = new HashSet<>();
int pairs = 0;
for(int i = 0; i < arr.length; i++) {
    if(!unmatched.add(arr[i])) {
        unmatched.remove(arr[i]);
        pairs++;
    }
}

Answer 2

Py3 solution for the problem using dictionaries

def sockMerchant(n, ar):
    pair = 0
    d = {}
    for i in ar:
        if i in d:
            d[i] += 1
        if i not in d:
            d[i] = 1
    print(d)
    for x in d:
        u = d[x]//2
        pair += u
    return pair

Answer 3

This works for java 8!!

static int sockMerchant(int n, int[] ar) {
        Set<Integer> list = new HashSet<Integer>();
        int count = 0;
        for(int i= 0; i < n; i++){
            if(list.contains(ar[i])){
                count++;
                list.remove(ar[i]);
            }
            else{
                list.add(ar[i]);
            }
        }
        return count;
    }

Answer 4

This is my simple code for beginners to understand using c++ which prints the count of numbers of pair in the user-defined vector:

#include <bits/stdc++.h>

using namespace std;

vector<string> split_string(string);

// Complete the sockMerchant function below.
int sockMerchant(int n, vector<int> ar) {
  int count=0;
  vector<int> x;
  for(int i=0;i<n;i++){
    if(ar[i]!=0)
    {
      for(int j=i+1;j<n;j++)
        {
          if(ar[i]==ar[j]){
            count++;
            ar[j]=0;
            break;
        }
    }}
  }
  return count;
}

int main()
{
  int a,b;
  vector<int> v;
  cin>>a;
  for(int i=0;i<a;i++){
    cin>>b;
    v.push_back(b);
    
  }
  cout<<sockMerchant(a,v);
}

Answer 5

package com.java.example.sock;

import java.io.IOException;
/**
 * 
 * @author Vaquar Khan
 *
 */
public class Solution1 {

// Complete the sockMerchant function below.
    /*
     * John works at a clothing store. He has a large pile of socks that he must pair by color for sale. Given an array of integers representing the color of each sock, determine how many pairs
     * of socks with matching colors there are.
     * For example, there are  socks with colors . There is one pair of color  and one of color . There are three odd socks left, one of each color. The number of pairs is .
     */
    static int sockMerchant(int n, int[] ar) {

        int counter = 0;
        int count = 0;
        //
        for (int i = 0; i < ar.length; i++) {
            count = 1;
            //
            for (int j = i + 1; j < ar.length; j++) {
                if (ar[i] == ar[j]) {
                    count++;
                }
            }

            if (count % 2 == 0) {
                counter++;
            }
        }

        return counter;
    }

    public static void main(String[] args) throws IOException {

        int array[] = { 10, 20, 20 ,10 ,10, 30, 50, 10 ,20};

        System.out.println(sockMerchant(9, array));
    }
}

Answer 6

Here my solution with JAVA for Sock Merchant test on HackerRank

import java.io.*;
import java.util.*;

public class sockMerchant {

public static void main(String[] args) {
    Scanner en = new Scanner(System.in);
    int n=en.nextInt();
    int[] hash = new int[300];
    for(int i=0; i<n; i++){
        hash[en.nextInt()]++;
    }
    long res=0;
    for(int f: hash){
        res+=f/2;
    }
    System.out.println(res);
 }
}

Answer 7

Refer below one using HashMap and having complexity O(1)

static int sockMerchant(int n, int[] ar) {
        int pairs=0;
        Map<Integer, Integer> map = new HashMap<>();
        for(int i=0;i<n;i++){
            if(map.containsKey(ar[i])){
                int count=map.get(ar[i]);
                map.put(ar[i],++count);
            }
            else{
                map.put(ar[i],1);
            }
        }
        for(int i : map.values()){
            pairs=pairs+(i/2);
        } 
        return pairs;

    }

Answer 8

static int sockMerchant(int n, int[] ar) {
    int pairs = 0;
    for (int i = 0; i < ar.length; i++) {
        int counter = 0;
        for (int j = 0; j < ar.length; j++) {
            if (j < i && ar[j] == ar[i]) break;
            if(ar[j]==ar[i]) counter++;
        }
        pairs+=counter/2;
    }
    return pairs;
}

Answer 9

Code for python 3

n = 9
ar = [10, 20, 20, 10, 10, 30, 50, 10, 20]
def sockMerchant(n, ar):
    totalpair = 0
    test= list(set(ar))
    for i in test:
        pair = 0
        for j in ar:
            if i==j:
                pair+=1
        if pair>=2:
            totalpair=totalpair+int(pair/2)
    return totalpair
print(sockMerchant(n,ar))

Answer 10

def sockMerchant(n, ar):

socks = dict()
pairs = 0
for i in ar:
    if i in socks:
        socks[i] = socks[i]+1
    if i not in socks:
        socks[i] = 1
    if socks[i]%2 == 0:
        pairs += 1

return pairs  

Answer 11

We can use a Hash Table, for it. As Hash Table's Complexity is O(1)
Look at below code snippet, i created a dictionary in python i.e. Hash Table having key and value. In dictionary, there only exists a unique Key for each value. So, at start dictionary will be empty. We will loop over the provided list and check values in dictionary keys. If that value is not in dictionary key, it means it is unique, add it to the dictionary. if we find value in dictionary key, simply increment pairs counter and remove that key value pair from hash table i.e. dictionary.

def sockMerchant(n, ar):
    hash_map = dict()
    pairs = 0
    for x in range(len(ar)):
        if ar[x] in hash_map.keys():
            del hash_map[ar[x]]
            pairs += 1
        else:
            hash_map.setdefault(ar[x])
    return pairs

Answer 12

This problem can be done easily with a hashset. We can take advantage of the HashSet's ability to not store duplicate elements. Here is the code below.

    Set<Integer> set = new HashSet<>();
    int pairCount = 0;
    for(int i = 0; i < arr.length; i++) {
        if(set.add(a[i])
           set.add(a[i])
        else {
           pairCount++; 
           set.remove(a[i]);
        }
    }
    return pairCount;

Answer 13

/*
 * Complete the 'sockMerchant' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts following parameters:
 *  1. INTEGER n
 *  2. INTEGER_ARRAY ar
 */

function sockMerchant(n, ar) {
    // Write your code here    
    let count = [];
    for (var i = 0; i < ar.length; i++) {
        if (count.hasOwnProperty(ar[i])) {
            count[ar[i]]++;
        }
        else {
            count[ar[i]] = 1;
        }
    }
    
    let number = 0;
    for (const key in count) {
        number += parseInt(count[key] / 2);
    }
    return number;
}

Answer 14

My answer in C
        int sockMerchant(int n, int ar_count, int* ar) {
        int matchcounter =0;// each number repeating count
        int paircounter=0;//total pair
        int size=0;int i,j,k;
        bool num_av=false;//number available or not in new array
        int numberarray[n];//creating new (same length) array of length n
       for(i=0;i<n;i++){
          num_av=false;
          for(k=0;k<=size;k++){
            if(numberarray[k] == ar[i]){
              num_av=true;
              break;  
            }
          }
          if(!num_av){
                size+=1;
                numberarray[size-1]=ar[i];
                for(j=0;j<n;j++){
                    if(ar[i]==ar[j]){
                        matchcounter++;
                    }
                }
                paircounter += matchcounter/2;
                matchcounter=0;
          }
           
       }
       return paircounter;
    }

Answer 15

I wanted to solve this using Array. Here is my solution for Sock Merchant problem on HackerRank (Java 8):

.... import org.apache.commons.lang3.ArrayUtils; import java.util.Arrays;

class Result {

public static int sockMerchant(int n, List<Integer> ar) {

int[] arr = ar.stream().mapToInt(i->i).toArray();

int counter = 0;

for(int i = 0; i<n; i++) {
    if(arr[i]>0) {
        int t = arr[i];
        arr[i] = -1;
        int j = ArrayUtils.indexOf(arr, t);
        if(j == -1) {
            continue;
        } else {
            arr[j] = -1;
            counter += 1;
        }
    } else {
        continue;
    }
}

return counter;    

}

}

This has a O(n) time complexity.

Answer 16

Code for Javascript

const set = new Set()
let count = 0;

for(let i = 0; i < i; i++) {
    if (set.has(ar[i])) {
        count++;
        set.delete(ar[i])
    } else {
        set.add(ar[i])
    }
}

Answer 17

function sockMerchant(n, ar) {
  //Need to initiate a count variable to count pairs and return the value
  let count = 0
  //sort the given array
  ar = ar.sort()
  //loop through the sorted array 
  for (let i=0; i < n-1; i++) {
    //if the current item equals to the next item 
    if(ar[i] === ar[i+1]){
      //then that's a pair, increment our count variable
      count++
      //also increment i to skip the next item
      i+=1
    }
  }
  //return the count value
  return count
}

sockMerchant(9, [10, 20, 20, 10, 10, 30, 50, 10, 20])

Answer 18

You can count the number of times a number appears in the list and divide them by 2

def sockMerchant(n, ar):
     unq = set(ar)
     count = 0
     for i in unq:
      count_vals = ar.count(i)
      if count_vals>1:
        count = count + int(count_vals/2)
     return count

Answer 19

The more easiest way I preferred. Answer in Kotlin

var counter = 0
for (i in 0 until n) {
    if (arr[i] != 0) {
        loop@ for (j in i + 1 until n) {
            if (arr[i] == arr[j]) {
                counter++
                arr[j] = 0
                break@loop
            }
        }
    }
}

Commenting for better programming

Answer 20

it can also be solved using the built in Set data type as below (my try) -

function sockMerchant(n, ar) {
    // Write your code here
    let numberSet = [...new Set(ar)];
    let pairs = 0;
    for(let i=0;i<numberSet.length;i++){
        let count = 0;
        ar.filter(x => {
           if(x == numberSet[i])
               count++;
        });
        pairs+= count / 2 >= 1 ? Math.trunc(count / 2) : 0;
    }
    return pairs;
}

Answer 21

Using Python 3:

def sockMerchant(n, ar):

    flag = 0
    for i in range(n):
        if ar[i:].count(ar[i])%2==0:
            flag+=1
    return flag

Answer 22

Think how you would do it in real life. If someone handed you these socks one-by-one, you'd like think, "Do I have one of these already?" If not, you'd set it down and move on to check on the next sock. When you find one you've already set down, you'd move the pair to the side and count that as another found pair.

Programmatically you may take advantage of a HashSet given it's quick access (constant) and that it only allows for one entry per unique key. Therefore, you can attempt add to the set. Failure to do so means it already exists, count and remove the pair, and continue.

Time-complexity: O(n) [n = number of socks]

Space-complexity: O(m) [m = number of UNIQUE sock types]

Java 8:

public static int sockMerchant(int n, List<Integer> ar) 
    {    
        Set<Integer> uniqueSockFound = new HashSet<Integer>(); 
        int countedPairs = 0;
        
        //Iterate through each sock checking if a match has been found already or not
        for(Integer sock: ar)
        {
            //If adding the sock to the set is a success, it doesn't exist yet
            //Otherwise, a pair exists, so remove the item and increment the count of pairs
            if(!uniqueSockFound.add(sock))
            {
                countedPairs++;
                uniqueSockFound.remove(sock);
            }
        }

        //Return count of pairs
        return countedPairs;
    }

Answer 23

For Javascript

function sockMerchant(n, ar) {
    // Create an initial variable to hold the pairs
    let pairs = 0;

    // create an object to temporarily assign pairs
    const temp = {};
    
    // loop through the provided array
    for (let n of ar) {

        // check if current value already exist in your temp object
        if (temp[n] in temp) {
            // if current value already exist in temp 
            // delete the value and increase pairs
            delete temp[n];
            pairs += 1;
        } else {
            // else add current value to the object
            temp[n] = n;
        }
    }

    // return pairs
    return pairs;
}

Answer 24

Yes, you can reduce the complexity of this to O(n). Iterate the input array just once and for each new element found create an entry in a hash map with a value of 1. If you find a repeated entry, increment the value of that entry in the map.

When you complete the pass, iterate the items in the map dividing their values by two, keep only the integer part of the division, and add the cumulative sum.

Answer 25

here is my solution and it worked for the given set of inputs.. import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int size = sc.nextInt(); int[] arr = new int[size]; for(int i=0 ; i<size ; i++){ arr[i] = sc.nextInt(); } int flag = 0; for(int j=0; j<size ; j++){ int count = 0; for(int i=j+1; i<size ; i++){ if(arr[j]==arr[i]){ count++; } } flag += count/2; } System.out.println(flag); } }