https://leetcode.com/problems/concatenation-of-consecutive-binary-numbers/

JavaScript 풀이

const concatenatedBinary = (n) => {
  const nums = [...Array(n).keys()].map((x) => x + 1); 

  return nums.reduce((acc, num) => {
    return (acc = acc * (1 << num.toString(2).length) + num) % (1e9 + 7);
  }, 0);

};

처음엔 나머지 값을 맨 마지막에 따로 취해줬는데 reduce 안에서 따로 계산해줬더니 통과함

discuss란에서 솔루션 봤고 혼자 풀라고 하면 못풀듯

설명 코드

Time Complexity: O(N)
Space Complexity: O(1)

class Solution {
public:
    // the idea is to use bit manipulation to set the current number based on the previous number
    // for example, 
    // n = 1, ans = 0b1
    // n = 2 (10), we need to shift 2 bits of the previous ans to the left and add `n`
    // i.e. 1 -> 100 (shift 2 bits to the left) -> 110 (set `10`). ans = 0b110
    // n = 3 (11), we need to shift 2 bits of the previous ans to the left and add `n` 
    // i.e 110 -> 11000 (shift 2 bits to the left) -> 11011 (set `11`). ans = 0b11011
    // n = 4 (100), we need to shift 3 bits of the previous ans to the left and add `n`
    // i.e. 11011 -> 11011000 (shift 3 bits to the left) -> 11011100 (set `100). ans = 0b11011100
    // so now we can see a pattern here
    // we need to shift `l` bits of the previous ans to the left and add the current `i` 
    // how to know `l`? it is not difficult to see `x` only increases when we meet power of 2
    int concatenatedBinary(int n) {
        // `l` is the bit length to be shifted
        int M = 1e9 + 7, l = 0;
        // use long here as it potentially could overflow for int
        long ans = 0;
        for (int i = 1; i <= n; i++) {
            // i & (i - 1) means removing the rightmost set bit
            // e.g. 100100 -> 100000
            //      000001 -> 000000
            //      000000 -> 000000
            // after removal, if it is 0, then it means it is power of 2
            // as all power of 2 only contains 1 set bit
            // if it is power of 2, we increase the bit length `l`
            if ((i & (i - 1)) == 0) l += 1;
            // (ans << l) means shifting the orginal answer `l` bits to th left
            // (x | i) means  using OR operation to set the bit
            // e.g. 0001 << 3 = 0001000
            // e.g. 0001000 | 0001111 = 0001111
            ans = ((ans << l) | i) % M;
        }
        return ans;
    }
};

자료형

알아야할 개념

• Bit shift << >> 연산자 https://www.interviewcake.com/concept/java/bit-shift
  https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Left_shift

• 2진법 <-> 10진법 완벽하게 안된다. (제한이 있다)

---

정리: 새롭게 안 것

https://velog.io/@ordo_92/수형-표현-Math-expression-JS 참고 (수형 표현 지수 표기에서 1e21은 걍 문자열 그대로 퉁침)

1e+20 100000000000000000000
1e+21 은 문자열대로 나옴

자스는 Number, BigInt로 숫자 저장하고 Number같은 경우에는 C언어 double이랑 같은 방식으로 저장됨 (부동소수점) 안전한 숫자...

2^53 까지 가능함

parseInt 본목적은 string을 number로 변환하는 것이라서 적합한 예는 아님....

그래서 shift 써서 풀이함!

The parseInt() function parses a string argument and returns an integer of the specified radix (the base in mathematical numeral systems).
parseInt는 문자열 표현을 가지고 수를 만드는 메서드임

parseInt("1000000000000000000000", 2) 이렇게 문자열로 나타내진 걸 바꾸는 거지
1e21을 2진법으로 바꾸는 거에 의미가 있지는 않음.
진법간 변환은 똑같은 수인데 문자열 표현을 바꾸거나, 별로 안 쓰지만 문자열 표현이 같은데 진법이 달라서 수가 달라지는 경우인데 지금 a, b 이런 애들을 수로 선언했기 때문에 달라질 수 있는 건 문자열 표현밖에 없고 그건 parseInt로 하는 게 아님

자스에서는 여기까지 숫자 표현 가능함....

---

걍 대박 쉽게
1~n까지 숫자 만들어서 각 요소마다 2진법으로 바꾸고 조인 시키면 안되나 라고 생각했는데 안된다.
왜 안돼지 하고 찾아봄..

ㅋㅋ 이게 미디움? 이지 아니야? 하면서 풀었는데 역시..
걍 내 뻘짓 코드 아카이브 (수치스럽지만... 이후의 내가 비웃어줘라..값이 작으면 답대로 나오는데 한 20부터 값이 이상하게 나오고 n 엣지포인트 찍으면 NaN 뜸)
이런 뻘짓을 기대하고 문제 만든듯

const concatenatedBinary = (n) => {
  const consecutiveNumbers = [...new Array(n).keys()].map((x) => x + 1);

  const concatedInBinary = consecutiveNumbers
    .map((x) => x.toString(2))
    .join("");

  return parseInt(concatedInBinary, 2) % (Math.pow(10, 9) + 7);

  // 아.. '100' 끝이 reverse 했을 때 '001' 이면 '1' 되니까 오류..
  //   const binaryToDecimal = [...concatedInBinary]
  //     .map((x) => Number(x))
  //     .reverse()
  //     .reduce((acc, cur, curIndex) => {
  //       return acc + 2 ** curIndex * cur;
  //     }, 0);

  return binaryToDecimal % (Math.pow(10, 9) + 7);
};

// int n returns decimal value
// 3 => [1, 2, 3]
// 2진법으로 바꾸면 [1, 10, 11]
// concat '11011'
// reverse 한 다음에 reduce해서 문제 풀이하면 될듯
// 아.. '100' 끝이 reverse 했을 때 '001' 이면 '1' 되니까 오류..

console.log(concatenatedBinary(42) === 632668867);