Count Of 3s

A basic approach will be to simply iterate through the range and keep a count of the occurrences of ‘3’ in each number of the range, and finally return it.

Algorithm:

1. Initialise a variable “count” to store the total occurrences of ‘3’ in the range.
2. Start traversing through the range from [0, N], and check for each digit of the number:
   • If the digit is ‘3’:
     • Increment “count”
   • Else:
     • Continue
3. Return “count”

In this approach instead of traversing through the complete range, we will be creating cases for every digit of ‘N’. Using simple mathematics and observation we will try to come up with a method to count occurrences of ‘3’ in the range of [0, N], by just working with the digits of ‘N’.

1. If we count generally then, we know ‘3’ comes 1 time in the range of [0, 10], that is a one-tenth portion. Meaning, approximately one-tenth of the time, the last digit will be ‘3’.
2. Similarly, we can say that any digit will be ‘3’ approximately one-tenth of the time.
   • For example in the range [0, 100], the 10’s digit occurs 10 times which is exactly one-tenth, but in a case let’s say [0, 44], ‘3’ occurs for much more than one-tenth of the range. We will be calculating the exact ratio of occurrences of ‘3’ to the range using the below cases:
3. Case 1: (When digit > 3)
   • In this case, let us suppose the index for which the digit is greater than ‘3’ is “idx”, then to calculate the number of ‘3’ in the “idx” digit, we can simply round it up, to the nearest 10 ^ (idx + 1), then finally divide it by 10.
4. Case 2: (When digit < 3)
   • In this case, rather than rounding up we will round down to the nearest 10 ^ (idx + 1), and again divide it by 10.
5. Case 3: (When digit = 3)
   • Now, for this case we will divide the complete number in two parts. We will round down the number to the nearest 10 ^ (idx + 1), and for the remaining right side of the number we will simply count the number of ‘3’.
6. Putting all these cases together in an algorithm we get:
   • When digit > 3:
     • if N[idx] > 3:
       • Count 3s in range at digit(N, idx) =
       • let y = roundup to nearest 10 ^ (idx + 1)
       • return y / 10
   • When digit < 3:
     • if N[idx] < 3:
       • Count 3s in range at digit(N, idx) =
       • let y = round down to nearest 10 ^ (idx + 1)
       • return y / 10
   • When digit = 3:
     • if N[idx] = 3:
       • Count 3s in range at digit(N, idx) =
       • let y = round down to nearest 10 ^ (idx + 1)
       • let z = right side of N (i.e., N % 10 ^ idx)
       • return y / 10 + z + 1
7. You simply need to traverse through each digit and follow the above algorithm.