2
\$\begingroup\$

Question: A binary string is given with only 0's and 1's. A number n is also given as the length of a sub string to be considered. It is to find the number of unique substrings. Here, n=3.

My algorithm: The ways I followed: (i) First, I extracted out the sub string of length 3 and converted it into a number. (ii) Then, I stored the number in a new integer type array. In this way, I had an integer array full of numbers representing the substrings. (iii) Lastly, I traversed down the array, keeping track of the occurrence of the unique numbers only. The amount of unique numbers therefore correspond to the number of unique substring.

#include<stdio.h>
#include <string.h>

int main(void)
{
    char arr[50];
    int o[50],check[10000];
    int i,j,count=1,l,k=0,sum,p;

    l=strlen(arr);

    for(i=0;i<l-2;i++){
        p=4;sum=0;
        for(j=0;j<3;j++){
            sum+=(arr[i+j]-'0')*p;
            p/=2;
        }
        o[k++]=sum;
    }

    memset(check,0,sizeof(check));

    for(i=0;i<k-1;i++){
        for(j=i+1;j<k;j++){
            if(o[i]!=o[j] && check[o[i]]!=1 && check[o[j]]!=1){
                count++;
                check[o[j]]=1;
            }
        }
        check[o[i]]=1;
    }

    printf("\n%d",count);

    return 0;
}

I think that my code is quite long and it could be shortened with a good optimization. But I can't think of a way.

\$\endgroup\$
3
  • \$\begingroup\$ How big the string, how vast be n? \$\endgroup\$ Nov 18, 2019 at 19:35
  • \$\begingroup\$ @chux I've edited the question... \$\endgroup\$ Nov 19, 2019 at 11:19
  • \$\begingroup\$ @chux sorry for the discomfort...I've considered n=3 here...I've cleared the question... \$\endgroup\$ Nov 19, 2019 at 16:21

1 Answer 1

1
\$\begingroup\$

Your code can be more efficient. For example, both nested for-loops can be replaced with single for-loops. In the first loop, the next sum can be calculated by left-shifting the previous sum, adding the new bit, and masking off n-bits. count[sum] is how many times an n-bit pattern == sum has been seen. So the second loop merely counts how many '1's are in count. Something like the code below (not tested).

int count_unique(char *arr, int n) {
    int mask = (1 << n) - 1;

    /* the size needs to be 2**n.  This works for n <= 10 */
    int count[1024];
    memset(count, 0, sizeof(count));

    int sum = 0;

    for (int i = 0; arr[i]; i++) {
        sum = ((sum << 1) | (arr[i] - '0')) & mask;

        if (i >= n - 1) {
            count[sum]++;
        }
    }

    int unique = 0;

    for (int i = 0; i < sizeof(count)/sizeof(int); i++) {
        if (count[i] == 1) {
           unique++;
        }
    }

    return unique;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.