Codility K-Sparse Test Spoilers

Have you tried the latest Codility test?

I felt like there was an error in the definition of what a K-Sparse number is that left me confused and I wasn't sure what the right way to proceed was. So it starts out by defining a K-Sparse Number:

In the binary number "100100010000" there are at least two 0s between any two consecutive 1s. In the binary number "100010000100010" there are at least three 0s between any two consecutive 1s. A positive integer N is called K-sparse if there are at least K 0s between any two consecutive 1s in its binary representation. (My emphasis)

So the first number you see, 100100010000 is 2-sparse and the second one, 100010000100010, is 3-sparse. Pretty simple, but then it gets down into the algorithm:

Write a function:

class Solution { public int sparse_binary_count(String S,String T,int K); }

that, given:

    string S containing a binary representation of some positive integer A,
    string T containing a binary representation of some positive integer B,
    a positive integer K.

returns the number of K-sparse integers within the range [A..B] (both ends included)

and then states this test case:

For example, given S = "101" (A = 5), T = "1111" (B=15) and K=2, the function should return 2, because there are just two 2-sparse integers in the range [5..15], namely "1000" (i.e. 8) and "1001" (i.e. 9).

Basically it is saying that 8, or 1000 in base 2, is a 2-sparse number, even though it does not have two consecutive ones in its binary representation. What gives? Am I missing something here?

Solution

Tried solving that one. The assumption that the problem makes about binary representations of "power of two" numbers being K sparse by default is somewhat confusing and contrary.

What I understood was 8-->1000 is 2 power 3 so 8 is 3 sparse. 16-->10000 2 power 4 , and hence 4 sparse.

Even we assume it as true , and if you are interested in below is my solution code(C) for this problem. Doesn't handle some cases correctly, where there are powers of two numbers involved in between the two input numbers, trying to see if i can fix that:

int sparse_binary_count (const string &S,const string &T,int K) 
{
    char buf[50];
    char *str1,*tptr,*Sstr,*Tstr;
    int i,len1,len2,cnt=0;
    long int num1,num2;
    char *pend,*ch;

    Sstr = (char *)S.c_str();
    Tstr = (char *)T.c_str();
    str1 = (char *)malloc(300001);
    tptr = str1;

    num1 = strtol(Sstr,&pend,2);
    num2 = strtol(Tstr,&pend,2);

    for(i=0;i<K;i++)
    {
        buf[i] = '0';
    }
    buf[i] = '\0';

    for(i=num1;i<=num2;i++)
    {
        str1 = tptr;

        if( (i & (i-1))==0)
        {
            if(i >= (pow((float)2,(float)K)))
            {
                cnt++;
                continue;
            }
        }
        str1 = myitoa(i,str1,2);

        ch = strstr(str1,buf);
        if(ch == NULL)
            continue;
        else
        {
            if((i % 2) != 0)
                cnt++;
        }

    }
    return cnt;
}

    char*  myitoa(int val, char *buf, int base){


    int i = 299999;
    int cnt=0;

    for(; val && i ; --i, val /= base)  
    {
        buf[i] = "0123456789abcdef"[val % base];
        cnt++;
    }
    buf[i+cnt+1] = '\0';
    return &buf[i+1];

}

Codility K-Sparse Test **Spoilers**

Codility K-Sparse Test Spoilers