Description
Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
Examples:
Example 1:
Input: n = 13
Output: 6
Example 2:
Input: n = 0
Output: 0Solution in Python
Approach:
We can approach this problem by analyzing each digit position of the number n. For each position, we count how many times ‘1’ appears in that specific place. The trick is to divide the number into the current digit, digits before it (higher digits), and digits after it (lower digits), and compute how many times ‘1’ would appear at each position.
Python
class Solution:
def countDigitOne(self, n: int) -> int:
# Initialize variables to keep track of the total number of 1's
count = 0
# We will use `factor` to track the current position (units, tens, hundreds, etc.)
factor = 1
while factor <= n:
# Split the number `n` into three parts:
# `higher` - digits higher than the current factor
# `current` - the current digit we are examining
# `lower` - digits lower than the current factor
higher = n // (factor * 10)
current = (n // factor) % 10
lower = n % factor
# If the current digit is 0, then 1 can appear only in the higher digits.
if current == 0:
count += higher * factor
# If the current digit is 1, then we have two parts:
# - For the higher digits, we have `higher * factor` times '1'.
# - For the lower digits, we add (lower + 1) since '1' can appear in the lower part.
elif current == 1:
count += higher * factor + (lower + 1)
# If the current digit is greater than 1, then 1 appears in both the higher digits and fills the current place.
else:
count += (higher + 1) * factor
# Move to the next digit position (tens, hundreds, thousands, etc.)
factor *= 10
# Return the total count of 1's
return countExplanation:
- Initialization:
- We initialize
countto zero. This will store the total count of digit ‘1’ appearances. factoris initialized to 1, which represents the current place we are analyzing (units, tens, hundreds, etc.).
- We initialize
- Loop:
- The
whileloop continues as long asfactoris less than or equal ton. This ensures we process each digit ofn.
- The
- Digit Analysis:
- For each digit, we compute
higher,current, andlower. These variables help us break the number into three parts:higher: All digits to the left of the current digit.current: The digit at the current place (units, tens, etc.).lower: All digits to the right of the current digit.
- For each digit, we compute
- Counting ‘1’s:
- Case 1: If
current == 0, then the digit ‘1’ can only appear in the higher digits. So, the count is updated byhigher * factor. - Case 2: If
current == 1, the count comes from two sources:- The digit ‘1’ appearing in the higher digits, which is
higher * factor. - The remaining part (lower digits) where ‘1’ appears, which is
lower + 1.
- The digit ‘1’ appearing in the higher digits, which is
- Case 3: If
current > 1, ‘1’ appears for both higher and the current position. So the count is incremented by(higher + 1) * factor.
- Case 1: If
- Incrementing factor: After processing each digit, we multiply
factorby 10 to move to the next place (units to tens, tens to hundreds, and so on).
Time Complexity:
- The algorithm processes each digit of the number
n, so the time complexity is O(log n), where log n is the number of digits inn. This is efficient enough to handle large inputs, up to 109.
This solution efficiently counts the occurrences of the digit ‘1’ across all numbers from 0 to n.
Solution in Javascript
JavaScript
var countDigitOne = function(n) {
// Initialize a counter to accumulate the number of 1's
let count = 0;
// Factor represents the current digit position (units, tens, hundreds, etc.)
let factor = 1;
// Continue the loop while factor is less than or equal to n
while (factor <= n) {
// Split n into three parts:
// `higher`: digits higher than the current place
// `current`: the digit at the current place (units, tens, hundreds, etc.)
// `lower`: digits lower than the current place
let higher = Math.floor(n / (factor * 10));
let current = Math.floor((n / factor) % 10);
let lower = n % factor;
// Case 1: If the current digit is 0, 1's appear only due to the higher digits
if (current === 0) {
count += higher * factor;
}
// Case 2: If the current digit is 1, 1's appear due to both higher and lower digits
else if (current === 1) {
count += higher * factor + (lower + 1);
}
// Case 3: If the current digit is greater than 1, 1's appear from higher digits and fill the current place
else {
count += (higher + 1) * factor;
}
// Move to the next place (units to tens, tens to hundreds, etc.)
factor *= 10;
}
// Return the total count of 1's
return count;
};Solution in Java
Java
class Solution {
public int countDigitOne(int n) {
// Initialize a variable to keep track of the total count of digit '1'
int count = 0;
// Factor represents the current digit position (units, tens, hundreds, etc.)
long factor = 1;
// Loop through each digit position while the factor is less than or equal to n
while (factor <= n) {
// Split the number n into three parts:
// `higher`: digits higher than the current place
// `current`: the current digit we're analyzing (units, tens, hundreds, etc.)
// `lower`: digits lower than the current place
long higher = n / (factor * 10);
long current = (n / factor) % 10;
long lower = n % factor;
// Case 1: If the current digit is 0, 1's appear only due to the higher digits
if (current == 0) {
count += higher * factor;
}
// Case 2: If the current digit is 1, 1's appear from both the higher digits and the lower part
else if (current == 1) {
count += higher * factor + (lower + 1);
}
// Case 3: If the current digit is greater than 1, 1's appear from higher digits and fill the current position
else {
count += (higher + 1) * factor;
}
// Move to the next place (units to tens, tens to hundreds, etc.)
factor *= 10;
}
// Return the total count of '1's
return count;
}
}Solution in C#
C#
public class Solution {
public int CountDigitOne(int n) {
// Initialize a variable to store the total count of digit '1'
int count = 0;
// Factor represents the current digit position (units, tens, hundreds, etc.)
long factor = 1;
// Loop through all the digit positions in n
while (factor <= n) {
// Split n into three parts:
// 'higher': digits to the left of the current digit
// 'current': the digit at the current position (units, tens, hundreds, etc.)
// 'lower': digits to the right of the current digit
long higher = n / (factor * 10);
long current = (n / factor) % 10;
long lower = n % factor;
// Case 1: If the current digit is 0, 1's only come from the higher digits
if (current == 0) {
count += (int)(higher * factor);
}
// Case 2: If the current digit is 1, 1's come from higher digits and the lower part
else if (current == 1) {
count += (int)(higher * factor + (lower + 1));
}
// Case 3: If the current digit is greater than 1, 1's appear in both higher and current place
else {
count += (int)((higher + 1) * factor);
}
// Move to the next digit position (units to tens, tens to hundreds, etc.)
factor *= 10;
}
// Return the total count of '1's
return count;
}
}