Codility K-Sparse Test **Spoilers**

Question

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?

Answer 1

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];

}

Answer 2

There was an information within the test details, showing this specific case. According to this information, any power of 2 is considered K-sparse for any K.

You can solve this simply by binary operations on integers. You are even able to tell, that you will find no K-sparse integers bigger than some specific integer and lower than (or equal to) integer represented by T.

As far as I can see, you must pay also a lot of attention to the performance, as there are sometimes hundreds of milions of integers to be checked.

My own solution, written in Python, working very efficiently even on large ranges of integers and being successfully tested for many inputs, has failed. The results were not very descriptive, saying it does not work as required within question (although it meets all the requirements in my opinion).

Answer 3

/////////////////////////////////////
solutions with bitwise operators:
no of bits per int = 32 on 32 bit system,check for pattern (for K=2, 
like 1001, 1000) in each shift and increment the count, repeat this 
for all numbers in range.




///////////////////////////////////////////////////////

int KsparseNumbers(int a, int b, int s) {
    int nbits = sizeof(int)*8;
    int slen = 0;
    int lslen = pow(2, s); 

    int scount = 0;
    int i = 0;
    for (; i < s; ++i) {
      slen += pow(2, i);
    }
    printf("\n slen = %d\n", slen);

    for(; a <= b; ++a) {
    int num = a;
      for(i = 0 ; i < nbits-2; ++i) {
         if ( (num & slen) == 0 && (num & lslen) ) {
          scount++;
          printf("\n Scount = %d\n", scount);
          break;
         }
       num >>=1;
      }
    }
return scount;

}

int main() {

   printf("\n No of 2-sparse numbers between 5 and 15 = %d\n", KsparseNumbers(5, 15, 2));

 }