Блог

Я пытаюсь решить проблему в leetcode, я взломал алгоритм для этой конкретной проблемы, написал псевдокод и реализовал код на C . В решении остается только один недостаток — modulo 1e9 7 результат.

Формулировка проблемы: учитывая целое число n, верните десятичное значение двоичной строки, сформированной путем объединения двоичных представлений от 1 до n по порядку, по модулю 1e9 7.

Мой подход :

Мой код :

 #include<math.h>
class Solution {
public:
    int concatenatedBinary(int n) {
        long long res = 0;
        for(int i=0;i<n;i  ){
            int lShift = (int)ceil(log((double)(i 1 1)));
            res = res << lShift;
            //problem lies between these 
            res %= 1000000007;
            res  = i 1;
            res %= 1000000007;
            cout << i << " - " << lShift << " - " << res << endl;
        }
        return res;
    }
};
 

Я не знаю, почему операция по модулю действует странно! Заранее спасибо.

 Example 1:

Input: n = 1
Output: 1
Explanation: "1" in binary corresponds to the decimal value 1. 

Example 2:

Input: n = 3
Output: 27
Explanation: In binary, 1, 2, and 3 corresponds to "1", "10", and "11".
After concatenating them, we have "11011", which corresponds to the decimal value 27.

Example 3:

Input: n = 12
Output: 505379714
Explanation: The concatenation results in "1101110010111011110001001101010111100".
The decimal value of that is 118505380540.
After modulo 109   7, the result is 505379714.
 

Ваша основная проблема заключалась в том, что вы использовали log вместо логарифма в базе 2: log2 .

Кроме того, в такой ситуации обычно лучше избегать вычислений с плавающей запятой.

В следующий код я включил исправленную версию вашего кода
и новую простую версию без каких-либо вычислений с плавающей запятой

 
#include<cmath>
#include <iostream>

class Solution {
public:
    int concatenatedBinary(int n) {
        long long res = 0;
        for(int i = 0; i < n; i  ){
            int lShift = (int)ceil(log2((double)(i 1 1)));
            res = res << lShift;
            //problem lies between these 
            res %= 1000000007;
            res  = i 1;
            res %= 1000000007;
            std::cout << i 1 << " - " << lShift << " - " << res << std::endl;
        }
        return res;
    }
    int concatenatedBinary_nolog(int n) {
        long long res = 0;
        int lShift = 1;
        int pow2 = 2;
        for(int i = 1; i <= n; i  ){
            if (i >= pow2) {
                lShift  ;
                pow2 *= 2;
            }
            res = res << lShift;
            res %= 1000000007;
            res  = i;
            res %= 1000000007;
            std::cout << i << " - " << lShift << " - " << res << std::endl;
        }
        return res;
    }
};

int main(){
    Solution sol;
    for (int n: {1, 3, 12}) {
        int answer = sol.concatenatedBinary(n);
        std::cout << n << " : " << answer << "n";
        answer = sol.concatenatedBinary_nolog(n);
        std::cout << n << " : " << answer << "n";
    }
}