Skip to content

Instantly share code, notes, and snippets.

@Mr-Kumar-Abhishek
Created October 13, 2016 17:21
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save Mr-Kumar-Abhishek/25e10156e38732b7a3ad50ef61d1b245 to your computer and use it in GitHub Desktop.
Sock Merchant algorithm
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
int main(){
int n;
scanf("%d",&n);
int *c = malloc(sizeof(int) * n);
for(int c_i = 0; c_i < n; c_i++){
scanf("%d",&c[c_i]);
}
// assuming number of count pairs is zero
int count_pair = 0;
// keep number of unique numbers
int unique_num = 1;
// creating a variable array for unique numbers
int *unique = malloc(sizeof(int)* unique_num);
// first number is always unique
unique[0] = c[0];
// contructing an array of unique numbers
for (int i = 1; i < n; i ++){ // excluding 0th value
int unique_flag = 0; // assuming flag is positive by default
// checking if assumpion of positivity is true
for (int j = 0; j < unique_num; j++) {
if (c[i] == unique[j]) {
unique_flag = 1;
}
}
// if the assumtion is true then increase the size of array by one unit
// and then place the unique value.
if (unique_flag == 0) {
// increase the number of unique items
unique_num++;
unique = realloc( unique, sizeof(int)* unique_num);
unique[unique_num - 1] = c[i]; // placing the unique value
}
}
for (int i = 0; i < unique_num; i++) { //counting number of each unique items
int count = 0;
for(int j = 0; j < n; j++){
if(unique[i] == c[j]){
count++;
}
}
count_pair = count_pair + (count/2); // making thier pairs and adding it to total numbers of pairs
}
printf("%d", count_pair); // finally,printing the result.
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment