Number of Ones
Calculating digits in a series of numbers.
Published on
/ lines long
In this post, I'll explain my solution to the programming puzzle from the latest issue(opens in new tab) of @cassidoo(opens in new tab)'s newsletter.
The task is simple:
Given an integer n, count the total number of 1 digits appearing in all nonnegative integers less than or equal to n.
Perhaps the most obvious solution is to just loop over the numbers, convert them to strings, and count the digits. But the larger the input number, the slower it gets. So, rather than counting, we can calculate the result.
Idea
Let's start with the number of times that the digit 1 appears in the 09 range. It's just one. The number 1.
Now, let's try 099. Here we have the same thing, with the difference being that it's repeated 10 times:
1, 11, 21, 31, 41, 51, 61, 71, 81, 91
↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ (10)
So, the units (rightmost digit) contributes to the sum with a total of 10 occurrences.
However, the range 1019 is special, because each number there always begins with 1:
10, 11, 12, 13, 14, 15, 16, 17, 18, 19
↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ (10)
In total, the digit 1 appears 20 times in the numbers up to 99:

10 times as a digit in the units column

10 times as a digit in the tens column
If we look at the numbers 0999, we'll start to see patterns. Now, 1 appears in the units column not 10, but 100 times:
1, 11, 21... 131, 141, 151... 321, 641, 961... 991
↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ (100)
Notice how we can just take the last digit off the number and get the number of times 1 will appear at the units position. For example, if we have 236, we can take the 6 out and know that 1 will surely appear 23 times as a units digit. In this case, however, we must add one, because 231 is also part of the collection. If the end number was 230, we wouldn't have that.
Now, we can do the same, but for the tens. If we remove the 36 from 236, we get 2. So we know that the digit 1 will cycle 2 times in the tens column:
1019, 110119
↑ ↑ ↑ ↑
But since the tens digit is 3, which is bigger than 1, we get one extra cycle, namely 210219. If we had 206, 0 is less than 1, so we wouldn't get that extra cycle.
The special case is when the digit is 1. If we have 216, then we get an incomplete extra cycle of only 7 repetitions, rather than 10. We go through 210216, not 210219. So the occurrences of 1 in the tens column depends on columns to the right. This time, we have to remove digits from the left side. For the number 216, we remove 21 from it and get 6. We then have to add 1, because even though 210 has 0 in the units, it still counts. We end up with 7, which is the number of ones in the incomplete cycle. Here's the entire calculation:
236
││└ 23*1 + 1*1 extra (because 6 > 1) = 24
│└─ 2*10 + 1*10 extra (because 3 > 1) = 30
└── 0*100 + 1*100 extra (because 2 > 1) = 100
total = 154
Notice how we have a multiplier for each digit, and it increases exponentially: 1 for units, 10 for tens, 100 for hundreds.
Implementation
Let's start with the multiplier. In code, we can loop over the digits in reverse to get it:
[6, 3, 2].forEach((digit, i) => {
let mul = Math.pow(10, i); // 1, 10, 100
});
Now, we have to be able to take digits out of the number. In our first iteration, for the units, we have to take 23 out of 236
. We can do that by dividing the number by 10, getting 23.6
. We can then round it down with Math.floor()
to get 23
.
For the tens, we have to get 2 out of 236
. We can do that by dividing by 100
, getting 2.36
, and rounding down to 2
.
Basically, we multiply our multiplier by 10, divide, then floor, and we have successfully taken out the necessary digits:
236
││└ mul = 1; 236/(mul*10) = 236/10 = 23.6; round(23.6) = 23;
│└─ mul = 10; 236/(mul*10) = 236/100 = 2.36; round(2.36) = 2;
└── mul = 100; 236/(mul*10) = 236/1000 = 0.23; round(0.23) = 0;
All that's left now is to apply the multiplier to those numbers and we get the number of complete cycles with a 1 that each digit goes through:
236
││└ 23*1 = 23
│└─ 2*10 = 20
└── 0*100 = 0
In code, we can do it like this:
let cycles = Math.floor(n / (mul * 10));
let ones = cycles * mul;
Now, we have to handle cases where the digit is greater than 1. That's when we have one extra cycle:
236
└─ 3 > 1 => extra cycle (210219)
206
└─ 0 < 1 => no extra cycle (we don't reach 210)
We add an extra if
statement:
let cycles = Math.floor(n / (mul * 10));
let ones = cycles * mul;
if (digit > 1) {
ones += mul; // add one extra cycle
}
Finally, we have the edge case where the digit is exactly 1
. This is where we have an incomplete cycle and the result depends on the digits to the right:
216
└─ just 1016, not 1019, so we extract 6
136
└── just 100136, not 100199, so we extract 36
We can get digits on the right by applying %
, the remainder operator(opens in new tab), to the number and the multiplier:
216 % 10 = divide by 10 and get the remainder => 6
136 % 100 = divide by 100 and get the remainder => 36
However, we must add 1 to that remainder, because we need to count the 0 as well. In other words, for the tens, we have:
210, 211, 212, 213, 214, 215, 216 => 7 numbers in total
└┴───────────────────────────────── this counts as well
So we need to extend our if
statement:
if (digit > 1) {
ones += mul; // add one extra cycle
} else if (digit === 1) {
ones += (n % mul) + 1; // incomplete cycle
}
Put together, our logic looks like this:
let n = 236;
let strings = n.toString().split(""); // ["2", "3", "6"]
let ints = strings.map((s) => parseInt(s)); // [2, 3, 6]
let digits = ints.reverse(); // [6, 3, 2]
let sum = 0;
digits.forEach((digit, i) => {
let mul = Math.pow(10, i);
let cycles = Math.floor(n / (mul * 10));
let ones = cycles * mul;
if (digit > 1) {
ones += mul; // add one extra cycle
} else if (digit === 1) {
ones += (n % mul) + 1; // incomplete cycle
}
sum += ones;
});
console.log(sum); // 154
Now, we can wrap that logic in an easily reusable function and use reduce()
(opens in new tab) to accumulate the sum:
function numberOfOnes(n) {
return n
.toString()
.split("")
.map((char) => parseInt(char))
.reverse()
.reduce((sum, digit, i) => {
const mul = Math.pow(10, i);
sum += Math.floor(n / (mul * 10)) * mul;
if (digit > 1) {
sum += mul;
} else if (digit === 1) {
sum += (n % mul) + 1;
}
return sum;
}, 0);
}
Here are some examples:
console.log(numberOfOnes(14)); // 7
console.log(numberOfOnes(236)); // 154
console.log(numberOfOnes(420)); // 192
console.log(numberOfOnes(1337)); // 812
console.log(numberOfOnes(65536)); // 36714
Play around with the code on CodePen(opens in new tab)!
Also, make sure to subscribe to rendezvous with cassidoo(opens in new tab) for similar puzzles and useful web development content.