Solution: Number Frequency

Grokking the Art of Recursion for Coding Interviews

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Number Frequency

Table of Contents

Contents are not accessible

Problem Statement

Write a Recursive Solution to Count occurrences of an Element in an Array.

Given an array of integers and a key element, write a recursive solution to count the occurrences of the key element in the array.

Examples:

Sr#	Array	Input Key	Output	Description
1	[2, 4, 6, 8, 4]	4	2	The key element 4 occurs twice in the array.
2	[1, 3, 5, 7, 9]	2	0	The key element 2 does not exist in the array.
3	[1, 2, 2, 2, 3]	2	3	The key element 2 occurs three times in the array.

Solution

Base Case:
- If the array is empty, return 0 because there are no occurrences of the key element.
Recursive Case:
- Compare the first element of the array with the key element.
  - If they are equal, increment the count by 1.
- Make a recursive call with the remaining subarray.
- Add the count from the recursive call to the current count and return the total count.

Code

Here is the code for this algorithm:

Python3

. . . .

Time and Space Complexity

The time complexity of the algorithm is $O(N)$ because, in the worst case, it needs to examine all elements of the array once. The space complexity of the algorithm is $O(N)$ because the recursive calls consume additional space on the call stack, and in the worst case, the depth of the call stack is proportional to the size of the array.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible