700418. Count Occurrence of digit k
Easy
Count Occurrence of digit k
Slug: find-number-of-numbers
Difficulty: Easy
Topic Tags: Arrays, Data Structures
Company Tags: None
Summary
This problem is about counting the occurrence of a given digit k in all numbers from 1 to n. The key concept involved here is arrays.
Detailed Explanation
The approach to this problem is quite straightforward. We iterate through each number from 1 to n, convert it to a string, and then count the occurrences of the digit k.
Here's a step-by-step breakdown of the solution:
- Initialize a variable
countto store the occurrence of the digitk. - Iterate through each number from 1 to
n. For each number:- Convert it to a string.
- Iterate through each character in the string (which represents a digit).
- If the current character is equal to the given digit
k, increment thecountvariable.
- Return the final value of
count.
Time complexity for this problem is O(n*m) where n is the range from 1 to n and m is the maximum number of digits in a number.
Space complexity is O(1) as we are not using any extra space that scales with input size.
Optimized Solutions
Java
public int countOccurrence(int n, char k) {
int count = 0;
for (int i = 1; i <= n; i++) {
String str = Integer.toString(i);
for (char c : str.toCharArray()) {
if (c == k) {
count++;
}
}
}
return count;
}