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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of counting occurrences in a sorted array

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

DSA Go

package main
import "fmt"

func countOccurrences(arr []int, x int) int {
    left, right := 0, len(arr)-1
    first, last := -1, -1

    // Find first occurrence
    for left <= right {
        mid := (left + right) / 2
        if arr[mid] == x {
            first = mid
            right = mid - 1
        } else if arr[mid] < x {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    if first == -1 {
        return 0
    }

    left, right = 0, len(arr)-1
    // Find last occurrence
    for left <= right {
        mid := (left + right) / 2
        if arr[mid] == x {
            last = mid
            left = mid + 1
        } else if arr[mid] < x {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return last - first + 1
}

func main() {
    arr := []int{1, 2, 3, 3, 3, 4, 5}
    fmt.Println(countOccurrences(arr, 3))
}

A 4

B 2

C 0

D 3

💡 Hint

Count how many times 3 appears consecutively in the sorted array.

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

🧠 Conceptual

intermediate

Understanding the binary search approach for counting occurrences

Why does the algorithm use two binary searches to count occurrences of an element in a sorted array?

A To find the first and last positions of the element, then calculate the count from these indices.

B To sort the array twice before counting the element.

C To count the element by checking every element twice.

D To find the middle element twice and sum their values.

💡 Hint

Think about how to find the range of the element's positions efficiently.

The two binary searches locate the first and last occurrence of the element, allowing calculation of total occurrences by subtracting indices.

🔧 Debug

advanced

Identify the error in counting occurrences code

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

DSA Go

package main
import "fmt"

func countOccurrences(arr []int, x int) int {
    left, right := 0, len(arr)-1
    first := -1

    // Find first occurrence
    for left <= right {
        mid := (left + right) / 2
        if arr[mid] == x {
            first = mid
            left = mid + 1 // Incorrect update
        } else if arr[mid] < x {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    if first == -1 {
        return 0
    }

    return 1
}

func main() {
    arr := []int{1, 2, 3, 3, 3, 4, 5}
    fmt.Println(countOccurrences(arr, 3))
}

A The code returns 0 even though 3 is present.

B The code causes a runtime panic due to index out of range.

C The code returns 1 instead of the correct count of 3.

D The code enters an infinite loop.

💡 Hint

Check how the first occurrence is found and what the function returns.

The code incorrectly updates 'left' when finding the first occurrence, causing it to find the last occurrence instead. Also, it returns 1 instead of the count.

❓ Predict Output

advanced

Output of counting occurrences for element not in array

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

DSA Go

package main
import "fmt"

func countOccurrences(arr []int, x int) int {
    left, right := 0, len(arr)-1
    first, last := -1, -1

    for left <= right {
        mid := (left + right) / 2
        if arr[mid] == x {
            first = mid
            right = mid - 1
        } else if arr[mid] < x {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    if first == -1 {
        return 0
    }

    left, right = 0, len(arr)-1
    for left <= right {
        mid := (left + right) / 2
        if arr[mid] == x {
            last = mid
            left = mid + 1
        } else if arr[mid] < x {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return last - first + 1
}

func main() {
    arr := []int{1, 2, 3, 3, 3, 4, 5}
    fmt.Println(countOccurrences(arr, 6))
}

A -1

B 0

C 1

D 5

💡 Hint

Check what happens when the element is not found in the array.

The element 6 is not in the array, so the first occurrence index remains -1 and the function returns 0.

🧠 Conceptual

expert

Time complexity of counting occurrences in a sorted array

What is the time complexity of counting occurrences of an element in a sorted array using the two binary searches approach?

A O(log n)

B O(n)

C O(n log n)

D O(1)

💡 Hint

Consider how many times the array is divided during binary search.

Each binary search runs in O(log n) time, and since two binary searches are performed, the total time complexity remains O(log n).