0% completed
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.
- Compare the first element of the array with the key element.
Code
Here is the code for this algorithm:
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.
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible