K-Sparse Test Codility ** Спойлеры **

Question

Вы пробовали последний тест Codility?

Я чувствовал, что в определении того, что такое число K-Sparse, произошла ошибка, которая оставила меня в замешательстве, и я не был уверен, каков был правильный путь. Итак, он начинается с определения K-разреженного числа:

В двоичном числе "100100010000" между двумя пробелами должно быть не менее двух любые два последовательных 1 с. В двоичном числе "100010000100010" есть по крайней мере три 0 между любыми двумя последовательными 1. Положительный целое число N называется K-разреженным, если между любыми любыми значениями K 0s два последовательных 1 с в двоичном представлении. (Мой акцент)

Итак, первое число, которое вы видите, 100100010000, является 2-разреженным, а второе, 100010000100010, является 3-разреженным. Довольно просто, но потом все сводится к алгоритму:

Написать функцию:

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

что дано:

    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.

возвращает число K-разреженных целых чисел в диапазоне [A..B] (оба концы включены)

и затем заявляет этот тестовый пример:

Например, для S = «101» (A = 5), T = «1111» (B = 15) и K = 2, функция должна возвращать 2, потому что есть только два 2-разреженных целых числа в диапазоне [5..15], , а именно "1000" (т.е. 8) и "1001" (то есть 9).

В основном это говорит о том, что 8 или 1000 в базе 2, это 2-разреженное число, даже если в двоичном представлении нет двух последовательных. Что дает? Я что-то здесь упускаю?

Answer 1

В деталях теста была информация, показывающая этот конкретный случай.Согласно этой информации, любая степень 2 считается K-разреженной для любого K.

. Это можно решить просто с помощью бинарных операций над целыми числами.Вы даже можете сказать, что вы не найдете K-разреженных целых чисел, больших, чем какое-то конкретное целое число и меньше (или равно) целому числу, представленному T.

Насколько я вижу, вы должны заплатитьтакже большое внимание к производительности, поскольку иногда нужно проверять сотни миллионов целых чисел.

Мое собственное решение, написанное на Python, очень эффективно работает даже с большими диапазонами целых чисел и успешно тестируется намного входов, не удалось.Результаты были не очень описательными, говоря, что они не работают должным образом в вопросе (хотя, по моему мнению, отвечают всем требованиям).

Answer 2

Пытался решить это. Предположение, что проблема состоит в том, что двоичные представления числа «степени двух» по умолчанию являются K разреженными, несколько запутанно и противоречиво.

То, что я понял, было 8 -> 1000 - это 2 степени 3, поэтому 8 - это 3 разреженных. 16 -> 10000 2 степени 4, а значит и 4 разреженных.

Даже если мы предполагаем, что это правда, и, если вас интересует ниже, мой код решения (C) для этой проблемы. Не правильно обрабатывает некоторые случаи, когда между двумя входными числами участвуют степени двух чисел, пытаясь понять, могу ли я это исправить:

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

 }