I am a beginner in C. My teacher gave me a homework problem in which a user would provide an array with its size.
What we have to do is:-
1) Take out all the distinct elements from that array.
2) Compare all the subarrays which are possible in the main array with the "distinct array".
3) Tell the number of times we were able to successfully "discover" all those subarrays which contained ALL the distinct elements.
Example:- We are given an array :- [1,2,2,3,3] The distinct elements array would be :- [1,2,3] All the subarray of the original array will be :-
1) [1,2]
2) [1,2,2]
3) [1,2,2,3]
4) [1,2,2,3,3]
5) [2,2]
6) [2,2,3]
7) [2,2,3,3]
8) [2,3]
9) [2,3,3]
10) [3,3]
The answer of this specific test case shall be 2. Since only (3) and (4) subarrays contain all the distinct elements i.e. 1,2 and 3.
Second Example:-
Given array :- [86,5,34,64,56,60,81,77,36,41]
The answer of the second example is 1; since all the elements of the original array are distinct and hence only one solution shall contain all the possible distinct elements which is the original array itself.
Here is my code which I have wrote for the above problem:-
# include <stdio.h>
# include <stdlib.h>
# include <stdbool.h>
bool check(int *, int *, int, int);
int main()
{
int number; // Variable name "number" which will specify the size of dynamically allocated array.
printf("Enter the size of your array\n");
scanf("%d",&number);
int *array;
array = (int*)calloc(number, sizeof(int)); // Dynamically allocated memory.
int *temp_array;
temp_array = (int*)calloc(number, sizeof(int)); // Temporary variable of original array.
int i,j=0; // Counter variables for loop.
printf("Enter the elements of arrays\n");
for(i = 0; i < number; i++)
{
scanf("%d",(array + i)); //Main original array being filled.
}
for(i = 0; i < number; i++)
{
*(temp_array + i) = *(array + i); //Copying into temp.
}
for(i = 0; i < number; i++)
{
for( j = i + 1 ; j < number; j++)
{
if( *(temp_array + i ) == *(temp_array + j))
{
*(temp_array + j) = 0; // My way of removing those numbers which are the repeated. (Assigning them value of zero).
}
}
}
i=0;j=0;
int sub_number = 0;
while(i < number)
{
if(*(temp_array + i) != 0)
{
sub_number++; // Variable name "sub_number" which will specify the size of dynamically allocated array "sub_array".
}
i++;
}
int *sub_array ;
sub_array = (int*)calloc(sub_number,sizeof(int));
j=0;
for(i = 0;i < number ;i++)
{
if( *(temp_array + i ) != 0)
{
*(sub_array + j) = * (temp_array + i ); //Transferring all the distinct values from temp_array to sub_array.
j++;
}
}
free(temp_array); //Freed "temp_array". No longer needed.
temp_array = NULL;
for(i = 0;i < sub_number; i++)
{
printf("%d ",*(sub_array + i)); // Desired array which only contains distinct and unique variables.
}
printf("\n");
int ans = 0; //Variable which shall calculate the answer.
int k=0; //New variable counter
j=0;
for(i=0; i < number; i++) //This loop will traverse variable "i" on array "array".
{
k = i;
while(k < number) //This loop will traverse variable "k" on array "array"
{
int *new_array;
new_array = (int*) calloc ((k-i+1),sizeof(int));
for(j = i; j <= k; j++) //This loop will assign the subset values of array "array" to array "new_array".
{
*(new_array + (j - i)) = *(array + j);
}
if(check(new_array, sub_array, (k-i+1), sub_number) == true) //This will check if ALL the values in "sub_array" are present in "new_array" or not.
{
ans++;
}
free(new_array);
new_array = NULL;
k++;
}
}
printf("%d",ans);
return 0;
}
bool check(int * new_array, int *sub_array, int new_number, int sub_number) //Function to check if ALL the values in "sub_array" are present in "new_array" or not.
{
int i = 0;
int j = 0;
for(i = 0; i < new_number; i++) //new_number is nothing but (k - i + 1)
{
if(*(new_array + i) == *(sub_array + j))
{
j++;
if(j == sub_number)
{
return true;
}
i = -1;
}
}
return false;
}
How to optimise this code? Is there any better way to implement this?
O(N)
see: leetcode.com/problems/subarrays-with-k-different-integers \$\endgroup\$1
. \$\endgroup\$[1,2,2,3,3]
. Sample output :-2
. \$\endgroup\$