Problem

You are given an integer n.

Return the total number of commas used when writing all integers from [1, n] (inclusive) in standard number formatting.

In standard formatting:

• A comma is inserted after every three digits from the right.
• Numbers with fewer than 4 digits contain no commas.

Constraints:

• 1 <= n <= 10^5

Examples:

• n = 1002 → 3. The numbers "1,000", "1,001", and "1,002" each contain one comma, giving a total of 3.
• n = 998 → 0. All numbers from 1 to 998 have fewer than four digits, so no commas are used.

Walkthrough

Ridiculous brute force

If you don't already know how, this is a good time to drop in here how in python you would print a number with the commas. This is done with f"{a_number:,}". The , modifier does this for us.

If we did that for every number we could literally construct the strings for the numbers between the range and count the commas.

Okay, let's go crazy and just do that using the f-string and the count() function. Only bit to note here is that range upper limit is n+1 because we want to include the value n.

1
2
3
4
5
6
7

class Solution:
  def countCommas(self, n: int) -> int:
    count = 0
    # n+1 because our endpoint should be inclusive.
    for number in range(1, n + 1):
      count += f"{number:,}".count(',')
    return count

Submission result

That submits and is successful, but as you would imagine that's painfully slow. The complexity is O(n log(n)) because we iterate through n numbers and the count() will iterate through the string checking each character, which will be log_10(n) (i.e., the number of digits).

Using logic

Rather than brute forcing this we can just use logic to partition the input space. Or you could pre-compute the values. The idea is the same.

Let's split up the values into the common number of commas they'll have:

The upper limit of n is only 100,000 though so we don't even need to go that far. Each value we check will contain either no commas or 1.

We need to check every value between 1 and n. We can reframe this problem to: "How many numbers in the range are greater than or equal to 1,000".

1
2
3
4
5
6
7
8

class Solution:
  def countCommas(self, n: int) -> int:
    if n >= 1000:
      # Note: 999 as we want 1000 - 999 = 1.
      return n - 999

    # Else all the numbers have no commas.
    return 0

Submission result

This is much better: O(1) time complexity all we have to do is inspect the input and we know the answer!

It's worth noting here that this is optimised for the upper bound of the input being 100,000. If they increased this upper bound it would no longer work because we may have numbers with 2+ commas that we're not catering for here. There's other techniques we'd use there, but let's not overcomplicate the solution.

Without branching

Sometimes people will go further than this. You could be asked: can we remove the branching? If you were working really low level this may be a performance boost - but in python you wouldn't care. But let's do it anyway.

1
2
3
4

class Solution:
  def countCommas(self, n: int) -> int:
    # All values < 999 will return negative numbers and be mapped to 0.
    return max(0, n - 999)

Submission result

People also think it's cool to write really short programs. Whilst this technically may be more optimal, it is actually a bit harder to maintain than the really obvious if branch version. So make sure time optimisation is what you want when you do something like this.