modulo operation not returning correct value

user_10305444 0
Viewed 140

I'm trying to solve a problem in leetcode, I have cracked the algorithm for that specific problem, written pseudo code, and implemented the code in C++. Just one flaw remains in the solution, modulo 1e9+7 the result.

The problem statetment : Given an integer n, return the decimal value of the binary string formed by concatenating the binary representations of 1 to n in order, modulo 1e9 + 7.

My approach :

my approach to concatenation-of-consecutive-binary-numbers

My code :

#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;
    }
};

I don't know why the modulo operation acting weirdly! Thanks in advance.

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.
modular-arithmetic bit-shift modulo c++
1 Answers

Your main problem was that you use log instead of a logarithm in base 2: log2.

Besides, it is generally better to avoid floating point calculations in such a situation.

In the following code, I have included a corrected version of your code,
and a new simple version without any floating point calculation


#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";
    }
}
user_105533410
Related