Codility - SparseBinaryDecomposition

#Tóm tắt

Bài này sẽ dùng tới các toán tử bitwise, cơ số hệ nhị phân để giải.
Sẽ hơi khó chút với bạn nào chưa quen, các bạn cứ vừa đọc code, vừa debug, vừa xem document là sẽ hiểu.
Còn khúc mắc chỗ nào thì cứ bình luận bên dưới nhen.

#Bài giải và kết quả

#Bài giải

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/**
 * 11000 => false
 * 10010 => true
 * @param {*} N
 * @returns
 */
function checkIsBinarySparse(N) {
  while (N) {
    if ((N & 1) === 0) {
      N >>= 1;
      continue;
    }

    if ((N >> 1) & 1) {
      return false;
    }
    N >>= 2;
  }

  return true;
}

/**
 * > 10001001001011100100
 * <- 10001001001010100100
 * @param {*} N
 * @returns
 */
function findSparseNumber(N) {
  let original = N;
  let currentBit = 0;
  let decreasedNumberToFindSparseNumber = 0;

  while (N) {
    if ((N & 1) === 0) {
      currentBit++;
      N >>= 1;
      continue;
    }

    if ((N >> 1) & 1) {
      decreasedNumberToFindSparseNumber += 2 ** (currentBit + 1);
    }

    currentBit += 2;
    N >>= 2;
  }

  return original - decreasedNumberToFindSparseNumber;
}

function execute(N) {
  let Q = N;
  if (!checkIsBinarySparse(Q)) Q = findSparseNumber(Q);

  let P = N - Q;
  if (checkIsBinarySparse(P)) {
    return Q;
  }

  return -1;
}

function solution(N) {
  console.time("executed time");
  const result = execute(N);
  console.timeLog("executed time");

  return result;
}

#Kết quả

Test cases
Performance tests

#Tài liệu liên quan