Created
October 13, 2016 17:21
Star
You must be signed in to star a gist
Sock Merchant algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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