Number of Ones

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 non-negative 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 0-9 range. It's just one. The number 1.

Now, let's try 0-99. 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 10-19 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 0-999, 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:

10-19, 110-119
↑  ↑    ↑   ↑

But since the tens digit is 3, which is bigger than 1, we get one extra cycle, namely 210-219. 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 210-216, not 210-219. 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 (210-219)

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 10-16, not 10-19, so we extract 6

136
└── just 100-136, not 100-199, 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.