Count Of 3s

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
10 upvotes
Asked in company
Facebook

Problem statement

You are given an integer ‘N’. You simply need to find out the number of occurrences of 3 as a digit in the range of numbers from [0, N].

Note: 
 You need to count occurrences at every place of the number.
For example : 
You are given N = 13, then the number of occurrences of 3 in range [0, 13] = 2 (3, 13), you need to return 2.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer ‘T’ which denotes the number of test cases or queries to be run. Then the test cases are as follows.

The first and only line of each test case contains a single integer ‘N’, denoting the higher limit of the range upto which you need to count the occurrences.
Output Format: 
For each test case, print a single integer that denotes occurrences of 3.

Print the output of each test case in a separate line.
Note: 
You don’t need to print anything; it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10^2
0 <= N <= 10^5

where ‘T’ is the number of test cases and 'N' is the given integer.

Time Limit: 1 sec
Sample Input 1:
2
13
24
Sample Output 1:
2
3
Explanation For Sample Input 1:
In the first test case, 
Number of occurrences of 3 in range [0, 13] = 2 (3, 13). Return 2

In the second test case, 
Number of occurrences of 3 in range [0, 24] = 3 (3, 13, 23). Return 3
Sample Input 2:
2
10
33
Sample Output 2:
1
8
Explanation For Sample Input 2:
In the first test case, 
Number of occurrences of 3 in range [0, 10] = 1 (3). Return 1

In the second test case, 
Number of occurrences of 3 in range [0, 33] = 8 (3, 13, 23, 30, 31, 32, 33). Return 8
Hint

Can you think of iterating through all numbers?

Approaches (2)
Brute Force

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”
Time Complexity

O(N * logN), where N is the given integer.

    

In this approach, we are traversing through the complete range and for every number, we are traversing through all of its digits. So, the overall time complexity of this approach becomes O(N * logN).

Space Complexity

O(1).

 

Since we are not using any extra space, the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Count Of 3s
Full screen
Console