leetcode-javascript/solutions/1067-digit-count-in-range.js at development · Anuj9826/leetcode-javascript · GitHub

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
/**
 * Digit Count In Range
 * Time Complexity: O(log(high))
 * Space Complexity: O(log(high))
 */
var digitsCount = function (d, low, high) {
  function quantifyDigitOccurrences(upperLimit) {
    if (upperLimit < 0) {
      return 0;
    }

    const currentNumberString = upperLimit.toString();
    const currentNumberLength = currentNumberString.length;
    let totalCountOfDigit = 0;

    for (
      let digitPosition = 0;
      digitPosition < currentNumberLength;
      digitPosition++
    ) {
      const leftPartStr = currentNumberString.substring(0, digitPosition);
      const leftPartNumeric = leftPartStr === "" ? 0 : parseInt(leftPartStr);

      const centralChar = currentNumberString[digitPosition];
      const centralDigitNumeric = parseInt(centralChar);

      const rightPartStr = currentNumberString.substring(digitPosition + 1);
      const rightPartNumeric = rightPartStr === "" ? 0 : parseInt(rightPartStr);

      const lengthOfRightPart = currentNumberLength - 1 - digitPosition;
      const baseTenPower = Math.pow(10, lengthOfRightPart);

      if (d === 0) {
        if (digitPosition === 0) {
          continue;
        }

        const contributionFromPrefixes = (leftPartNumeric - 1) * baseTenPower;

        if (centralDigitNumeric > d) {
          totalCountOfDigit += contributionFromPrefixes + baseTenPower;
        } else if (centralDigitNumeric === d) {
          totalCountOfDigit += contributionFromPrefixes + rightPartNumeric + 1;
        } else {
          totalCountOfDigit += contributionFromPrefixes + baseTenPower;
        }
      } else {
        const contributionFromEarlierBlocks = leftPartNumeric * baseTenPower;

        if (centralDigitNumeric > d) {
          totalCountOfDigit += contributionFromEarlierBlocks + baseTenPower;
        } else if (centralDigitNumeric === d) {
          totalCountOfDigit +=
            contributionFromEarlierBlocks + rightPartNumeric + 1;
        } else {
          totalCountOfDigit += contributionFromEarlierBlocks;
        }
      }
    }
    return totalCountOfDigit;
  }

  return quantifyDigitOccurrences(high) - quantifyDigitOccurrences(low - 1);
};