Skip to content

Instantly share code, notes, and snippets.

@Isa-rentacs
Last active January 20, 2018 06:53
Show Gist options
  • Save Isa-rentacs/3744095218ee892031153ad14ede3dec to your computer and use it in GitHub Desktop.
Save Isa-rentacs/3744095218ee892031153ad14ede3dec to your computer and use it in GitHub Desktop.
#include <stdio.h>
#include <stdlib.h>
void diffOfSets(char* setA, int lenA, char* setB, int lenB, char** setDiff, int* lenDiff)
{
int *countDiff = malloc(sizeof(int) * 26);
int *isIncludedArray = malloc(sizeof(int) * lenA);
int includedItemCount = 0;
for(int i=0;i<26;++i)
{
countDiff[i] = 0;
}
for(int i=0;i<lenA;++i)
{
countDiff[setA[i] - 'a']++;
}
for(int i=0;i<lenB;++i)
{
countDiff[setB[i] - 'a']--;
}
for(int i=0;i<26;++i)
{
if(countDiff[i] > 0)
{
includedItemCount++;
}
}
*setDiff = (char *)malloc(sizeof(char) * includedItemCount);
int addedItemCount = 0;
for(int i=0;i<26;++i)
{
if(countDiff[i] > 0)
{
(*setDiff)[addedItemCount] = i + 'a';
addedItemCount++;
}
}
*lenDiff = includedItemCount;
/* O(mn) solution
for(int i=0;i<lenA;++i)
{
int isIncluded = 1;
printf("i = %d\n", i);
for(int j=0;j<lenB;++j)
{
printf("j = %d\n", j);
if(setA[i] == setB[j])
{
isIncluded = 0;
break;
}
}
if(isIncluded == 1)
{
isIncludedArray[i] = 1;
includedItemCount++;
}
}
*setDiff = (char *)malloc(sizeof(char) * includedItemCount);
int addedItemCount = 0;
for(int i=0;i<lenA;++i)
{
if(isIncludedArray[i] == 1)
{
(*setDiff)[addedItemCount] = setA[i];
addedItemCount++;
}
}
*lenDiff = includedItemCount;
*/
}
int main(void) {
char* ansArray;
int ansCount;
char A[] = {'z', 'c', 'f'};
int countA = 3;
char B[] = {'a', 'b', 'e', 'z'};
int countB = 4;
printf("ansArray = %x\n", ansArray);
diffOfSets(A, countA, B, countB, &ansArray, &ansCount);
for(int i=0;i<ansCount;++i)
{
printf("%c", ansArray[i]);
}
printf("\n");
printf("%d\n", ansCount);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment