Grokking the Art of Recursion for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Number Frequency
On this page

Problem Statement

Examples:

Solution

Code

Time and Space Complexity

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#ArrayInput KeyOutputDescription
1[2, 4, 6, 8, 4]42The key element 4 occurs twice in the array.
2[1, 3, 5, 7, 9]20The key element 2 does not exist in the array.
3[1, 2, 2, 2, 3]23The key element 2 occurs three times in the array.

Solution

  1. Base Case:
    • If the array is empty, return 0 because there are no occurrences of the key element.
  2. 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.
Image

Code

Here is the code for this algorithm:

Python3
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!

On this page

Problem Statement

Examples:

Solution

Code

Time and Space Complexity