[leetcode] Concatenation of Consecutive Binary Numbers

victor·2021년 1월 28일
0

알고리즘

목록 보기
20/63

Problem

Code

/**
 * @param {number} n
 * @return {number}
 */

var concatenatedBinary = function(n) {
    const modulo = BigInt(Math.pow(10, 9) + 7);
    const binaryStr = concat(n, '');
  
    // case 1: using Util function: Time Limit Exceeded 311
    const big = parseBigInt(binaryStr, 2) % modulo;  
  
    // case 2: use Bigint: Time Limit Exceeded 281
  	const big = BigInt('0b' + binaryStr) % modulo;
  
    return parseInt(big);
};

// recursion
var concat = (n, str) => {
    if (n == 0) return str; 
    const bi = n.toString(2);
    str = bi.concat(str);
    n--;
    return concat(n, str);
}

// Util function: large binary string to integer
function parseBigInt(str, base=10) {
  base = BigInt(base)
  var bigint = BigInt(0)
  for (var i = 0; i < str.length; i++) {
    var code = str[str.length-1-i].charCodeAt(0) - 48; if(code >= 10) code -= 39
    bigint += base**BigInt(i) * BigInt(code)
  }
  return bigint
}

  • Complexity
    Time: O(N) x =>
    Space: O(1) x =>
profile
캬-!

0개의 댓글