This is the 24th day of my participation in the August Text Challenge.More challenges in August

Note: Part of the article content and pictures from the network, if there is infringement please contact me (homepage public number: small siege lion learning front)

By: Little front-end siege lion, home page: little front-end siege lion home page, source: Nuggets

GitHub: P-J27, CSDN: PJ wants to be a front-end siege lion

Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.

LeetCode 233. Number of digits 1 – JavaScript

Topic describes

Given an integer n, count the number of occurrences of the number 1 in all non-negative integers less than or equal to n.

Subject analysis

When the input is 13, the result is 6. Because 1 appears six times in the following numbers: 1, 10, 11, 12, 13.

Directly think of the violence method from 1 to N, and by modular operation to calculate the number of 1 in each number, and finally count the total. This method will get results, but will TLE.

Solution :(regular problem)

The correct solution is to observe the law and calculate by bit.

For the sake of illustration, for a number n, the digits increase from right to left, and the rightmost digit is 1. If the current bit is a bit, then the highest digit is: from bit+1 to the highest digit; The lowest digit is: bit-1 digit to the lowest digit. For example, for 213, if bit is 2 (the second bit from right to left), then the high digit is 2, the low digit is 3, and the current digit x is 1.

If we calculate the number of digits with 1 in the first bit of all digits less than or equal to n, we should discuss three cases:

  • ifx === 1, then the number of 1s contained in the first bit is:High digit * 10 ^ (bit-1) + (1 + low digit)
  • ifx < 1, then the number of 1s contained in the first bit is:High digit * 10 ^ (bit-1)
  • ifx > 1, then the number of 1s contained in the first bit is:(high digit + 1) * 10^(bit-1)

The code implementation is as follows:

var countDigitOne = function(n) {
  if (n < 0) {
    return 0;
  }

  let bit = 1;
  let res = 0;
  let high = n;
  while (high) {
    // High digit: from the first bit+1 bit to the highest bit
    high = Math.floor(n / Math.pow(10, bit));
    // From bit to highest bit
    let tmp = Math.floor(n / Math.pow(10, bit - 1));
    / / the current position
    let current = tmp % 10;
    // Lowest digit: from bit-1 to lowest digit
    let low = n - tmp * Math.pow(10, bit - 1);

    // Take the second digit, 213, as an example
    if (current === 1) {
      res = res + (low + 1) + high * Math.pow(10, bit - 1);
    } else if (current > 1) {
      res = res + (high + 1) * Math.pow(10, bit - 1);
    } else {
      res = res + high * Math.pow(10, bit - 1);
    }
    ++bit;
  }

  return res;
};
Copy the code

Thank you for reading, I hope to help you, if there is a mistake or infringement of the article, you can leave a message in the comment area or add a public number in my home page to contact me.

Writing is not easy, if you feel good, you can “like” + “comment” thanks for your support ❤