Count Occurrences of Element in Sorted Array in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of count occurrences function with duplicates

What is the output of the following C++ code that counts occurrences of 3 in a sorted array?

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>

int countOccurrences(const std::vector<int>& arr, int x) {
    auto first = std::lower_bound(arr.begin(), arr.end(), x);
    auto last = std::upper_bound(arr.begin(), arr.end(), x);
    return last - first;
}

int main() {
    std::vector<int> data = {1, 2, 3, 3, 3, 4, 5};
    std::cout << countOccurrences(data, 3) << std::endl;
    return 0;
}

A 2

B 3

C 1

D 0

💡 Hint

Use lower_bound and upper_bound to find the range of the element.

The element 3 appears three times consecutively in the sorted array. lower_bound finds the first 3, upper_bound finds the position after the last 3, so the difference is 3.

❓ Predict Output

intermediate

Count occurrences of element not present in array

What is the output of this C++ code counting occurrences of 6 in a sorted array?

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>

int countOccurrences(const std::vector<int>& arr, int x) {
    auto first = std::lower_bound(arr.begin(), arr.end(), x);
    auto last = std::upper_bound(arr.begin(), arr.end(), x);
    return last - first;
}

int main() {
    std::vector<int> data = {1, 2, 3, 4, 5};
    std::cout << countOccurrences(data, 6) << std::endl;
    return 0;
}

A 5

B 1

C -1

D 0

💡 Hint

If element is not found, lower_bound and upper_bound will be equal.

Since 6 is not in the array, lower_bound and upper_bound point to the same position, so the count is zero.

🔧 Debug

advanced

Identify the error in counting occurrences code

What error does the following C++ code produce when counting occurrences of 3 in a sorted array?

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>

int countOccurrences(const std::vector<int>& arr, int x) {
    auto first = std::lower_bound(arr.begin(), arr.end(), x);
    auto last = std::upper_bound(arr.begin(), arr.end(), x);
    return first - last;
}

int main() {
    std::vector<int> data = {1, 2, 3, 3, 3, 4, 5};
    std::cout << countOccurrences(data, 3) << std::endl;
    return 0;
}

A Negative number output

B SyntaxError

C Compilation error due to invalid subtraction

D Zero output

💡 Hint

Check the order of subtraction between iterators.

The code subtracts last - first in reverse order, resulting in a negative count.

❓ Predict Output

advanced

Count occurrences with all elements same

What is the output of this C++ code counting occurrences of 7 in an array where all elements are 7?

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>

int countOccurrences(const std::vector<int>& arr, int x) {
    auto first = std::lower_bound(arr.begin(), arr.end(), x);
    auto last = std::upper_bound(arr.begin(), arr.end(), x);
    return last - first;
}

int main() {
    std::vector<int> data(10, 7);
    std::cout << countOccurrences(data, 7) << std::endl;
    return 0;
}

A 10

B 0

C 1

D 9

💡 Hint

All elements are the target value.

Since all 10 elements are 7, the count is 10.

🧠 Conceptual

expert

Why use binary search for counting occurrences in sorted array?

Why is binary search preferred over linear search to count occurrences of an element in a sorted array?

A Binary search can count occurrences without checking elements

B Binary search uses less memory than linear search

C Binary search reduces time complexity from O(n) to O(log n) by exploiting sorted order

D Binary search works only on unsorted arrays

💡 Hint

Think about how sorted order helps search faster.

Binary search quickly finds the range of the element in O(log n) time, unlike linear search which checks each element in O(n).