<Codesignal> Numbers of Clans

Medium

Let's call two integers A and B friends if each integer from the array divisors is either a divisor of both A and B or neither A nor B. If two integers are friends, they are said to be in the same clan. How many clans are the integers from 1 to k, inclusive, broken into?

Example

For divisors = [2, 3] and k = 6, the output should be
numberOfClans(divisors, k) = 4.

The numbers 1 and 5 are friends and form a clan, 2 and 4 are friends and form a clan, and 3 and 6 do not have friends and each is a clan by itself. So the numbers 1 through 6 are broken into 4 clans.

Input/Output

• [execution time limit] 0.5 seconds (c)

• [input] array.integer divisors

  A non-empty array of positive integers.

  Guaranteed constraints:
  2 ≤ divisors.length < 10,
  1 ≤ divisors[i] ≤ 10.

• [input] integer k

  A positive integer.

  Guaranteed constraints:
  5 ≤ k ≤ 10.

• [output] integer

[C] Syntax Tips

// Prints help message to the console
// Returns a string
char * helloWorld(char * name) {
    char * answer = malloc(strlen(name) + 8);
    printf("This prints to the console when you Run Tests");
    strcpy(answer, "Hello, ");
    strcat(answer, name);
    return answer;
}

---

Solution

// Arrays are already defined with this interface:
// typedef struct arr_##name {
//   int size;
//   type *arr;
// } arr_##name;
//
// arr_##name alloc_arr_##name(int len) {
//   arr_##name a = {len, len > 0 ? malloc(sizeof(type) * len) : NULL};
//   return a;
// }
//
//
int numberOfClans(arr_integer divisors,int k)
{
	int count=0;
	arr_boolean numbers=alloc_arr_boolean(k+1);
	for(int i=0;i<=k;i++)
		numbers.arr[i]=false;

	for(int i=1;i<=k;i++)
		if(numbers.arr[i]==false)
		{
			count++;

			for(int j=i+1;j<=k;j++)
			{
				bool isSame=true;

				for(int d=0;d<divisors.size;d++)
					if(i%divisors.arr[d]==0 && j%divisors.arr[d]!=0 || i%divisors.arr[d]!=0 && j%divisors.arr[d]==0)
					{
						isSame=false;
						break;
					}

				if(isSame)
					numbers.arr[j]=true;
			}
		}

	return count;
}