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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of counting occurrences using binary search

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

DSA C

#include <stdio.h>

int firstOccurrence(int arr[], int n, int x) {
    int low = 0, high = n - 1, result = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == x) {
            result = mid;
            high = mid - 1;
        } else if (arr[mid] < x) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}

int lastOccurrence(int arr[], int n, int x) {
    int low = 0, high = n - 1, result = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == x) {
            result = mid;
            low = mid + 1;
        } else if (arr[mid] < x) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}

int countOccurrences(int arr[], int n, int x) {
    int first = firstOccurrence(arr, n, x);
    if (first == -1) return 0;
    int last = lastOccurrence(arr, n, x);
    return last - first + 1;
}

int main() {
    int arr[] = {1, 2, 3, 3, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 3;
    printf("%d\n", countOccurrences(arr, n, x));
    return 0;
}

A 3

B 2

C 4

D 0

💡 Hint

Count how many times 3 appears in the array {1, 2, 3, 3, 3, 4, 5}.

The number 3 appears three times consecutively in the array at indices 2, 3, and 4. The code finds the first and last occurrence indices and returns their difference plus one.

❓ Predict Output

intermediate

Output when element is not present

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

DSA C

int arr[] = {1, 2, 3, 3, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 6;
printf("%d\n", countOccurrences(arr, n, x));

A 6

B 1

C -1

D 0

💡 Hint

If the element is not found, the count should be zero.

Since 6 is not in the array, firstOccurrence returns -1, so countOccurrences returns 0.

🧠 Conceptual

advanced

Why binary search is efficient for counting occurrences in sorted arrays

Why is binary search a good choice to count occurrences of an element in a sorted array?

A Because it uses extra memory to store counts for each element.

B Because it sorts the array first, making counting easier.

C Because it finds the first and last positions in O(log n) time, avoiding scanning the whole array.

D Because it checks every element one by one to count occurrences.

💡 Hint

Think about how binary search divides the search space.

Binary search quickly narrows down the position of the element's first and last occurrence in logarithmic time, which is faster than scanning all elements.

🔧 Debug

advanced

Identify the bug in this counting occurrences code

What error will this code produce when counting occurrences of 3 in the array?

DSA C

#include <stdio.h>

int countOccurrences(int arr[], int n, int x) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] == x) count++;
    }
    return count;
}

int main() {
    int arr[] = {1, 2, 3, 3, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 3;
    printf("%d\n", countOccurrences(arr, n, x));
    return 0;
}

A Prints 0 because count is never incremented

B Runtime error due to accessing out-of-bounds array index

C Compilation error due to missing semicolon

D Prints 3 correctly

💡 Hint

Check the loop boundary condition carefully.

The loop runs from i = 0 to i <= n, which accesses arr[n], an invalid index causing runtime error.

🚀 Application

expert

Count occurrences in a large sorted array efficiently

You have a sorted array of 1 million integers. Which approach is best to count occurrences of a number efficiently?

A Use binary search to find first and last occurrence, then calculate count

B Sort the array first, then count occurrences by scanning

C Scan the entire array from start to end counting matches

D Use a hash map to store counts of all elements

💡 Hint

Consider time complexity for large data.

Binary search finds boundaries in O(log n) time, much faster than scanning or sorting again.

Practice

1. What is the main advantage of using a binary search approach to count occurrences of an element in a sorted array?

easy

A. It uses less memory than linear search

B. It sorts the array automatically

C. It reduces the search time from linear to logarithmic

D. It works only on unsorted arrays

Solution

1. Step 1: Understand binary search efficiency

   Binary search divides the search space in half each time, reducing time complexity to O(log n).

2. Step 2: Compare with linear search

   Linear search checks each element one by one, taking O(n) time, which is slower for large arrays.

3. Final Answer:

   It reduces the search time from linear to logarithmic -> Option C

4. Quick Check:

   Binary search = faster search [OK]

Hint: Binary search halves search space each step [OK]

Common Mistakes:

• Thinking binary search sorts the array
• Confusing memory usage with speed
• Assuming binary search works on unsorted arrays

2. Which of the following C code snippets correctly declares a function to count occurrences of an integer in a sorted array?

easy

A. void countOccurrences(int arr[], int n, int x);

B. int countOccurrences(int arr[], int n, int x);

C. int countOccurrences(int arr, int n, int x);

D. int countOccurrences(int arr[], int x);

Solution

1. Step 1: Check function return type and parameters

   The function should return an int (count), take array, size, and target element as parameters.

2. Step 2: Validate parameter types

   Array parameter must be int arr[] or int *arr, size as int n, and target as int x.

3. Final Answer:

   int countOccurrences(int arr[], int n, int x); -> Option B

4. Quick Check:

   Correct function signature = int countOccurrences(int arr[], int n, int x); [OK]

Hint: Function returns count as int, array passed as int[] [OK]

Common Mistakes:

• Using void return type instead of int
• Passing array as int instead of int[]
• Missing array size parameter

3. What will be the output of the following C code snippet?

int arr[] = {1, 2, 2, 2, 3, 4, 5};
int n = 7;
int x = 2;
int count = 0;
for (int i = 0; i < n; i++) {
    if (arr[i] == x) count++;
}
printf("%d", count);

medium

A. 1

B. 2

C. 4

D. 3

Solution

1. Step 1: Iterate through the array and count matches

   Elements equal to 2 are at indices 1, 2, and 3, so count increments 3 times.

2. Step 2: Print the count

   The final count is 3, so printf outputs 3.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Count of 2 in array = 3 [OK]

Hint: Count elements equal to x by scanning array once [OK]

Common Mistakes:

• Counting only first occurrence
• Off-by-one errors in loop
• Printing count before loop ends

4. Identify the error in the following C function intended to count occurrences of x in a sorted array using binary search:

int countOccurrences(int arr[], int n, int x) {
    int count = 0;
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == x) {
            count++;
            mid++;
        } else if (arr[mid] < x) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return count;
}

medium

A. Incrementing mid inside the loop does not change low or high

B. The loop condition should be low < high

C. count should be initialized to -1

D. The function should return void

Solution

1. Step 1: Analyze loop variables and updates

   Incrementing mid does not affect low or high, so loop may become infinite or incorrect.

2. Step 2: Understand binary search update rules

   To move search window, low or high must be updated, not mid.

3. Final Answer:

   Incrementing mid inside the loop does not change low or high -> Option A

4. Quick Check:

   mid++ does not move search window [OK]

Hint: Update low/high, not mid, to move binary search window [OK]

Common Mistakes:

• Changing mid instead of low/high
• Wrong loop condition causing infinite loop
• Incorrect return type

5. Given a sorted array arr = {1, 2, 2, 2, 3, 3, 4, 5, 5, 5, 5}, write a function that uses binary search to count occurrences of x = 5. What is the count returned?

hard

A. 4

B. 6

C. 5

D. 3

Solution

1. Step 1: Use binary search to find first occurrence of 5

   First 5 is at index 7.

2. Step 2: Use binary search to find last occurrence of 5

   Last 5 is at index 10.

3. Step 3: Calculate count as last - first + 1

   Count = 10 - 7 + 1 = 4.

4. Final Answer:

   4 -> Option A

5. Quick Check:

   Count of 5 in array = 4 [OK]

Hint: Count = last index - first index + 1 using binary search [OK]

Common Mistakes:

• Counting total elements instead of occurrences
• Off-by-one errors in count calculation
• Using linear search instead of binary search