First and Last Occurrence of Element in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Find first and last occurrence of 3 in a sorted array

What is the output of the following C code that finds the first and last occurrence of the number 3 in the 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 main() {
    int arr[] = {1, 2, 3, 3, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 3;
    int first = firstOccurrence(arr, n, x);
    int last = lastOccurrence(arr, n, x);
    printf("First: %d, Last: %d\n", first, last);
    return 0;
}

A First: -1, Last: -1

B First: 3, Last: 5

C First: 1, Last: 3

D First: 2, Last: 4

💡 Hint

Remember that array indexing starts at 0 and the array is sorted.

The first occurrence of 3 is at index 2 and the last occurrence is at index 4 in the array.

❓ Predict Output

intermediate

Output when element is not present

What will be the output of the code when searching for element 6 in the 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 main() {
    int arr[] = {1, 2, 3, 3, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 6;
    int first = firstOccurrence(arr, n, x);
    int last = lastOccurrence(arr, n, x);
    printf("First: %d, Last: %d\n", first, last);
    return 0;
}

A First: 6, Last: 6

B First: -1, Last: -1

C First: 5, Last: 6

D First: 0, Last: 0

💡 Hint

If the element is not found, the functions return -1.

Since 6 is not in the array, both first and last occurrence functions return -1.

🔧 Debug

advanced

Identify the bug in lastOccurrence function

What is the bug in the following lastOccurrence function that causes incorrect output?

DSA C

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;
}

A The loop condition should be 'low <= high' instead of 'low < high'

B The result variable is not updated when arr[mid] > x

C The mid calculation should be 'mid = (low + high + 1) / 2' to avoid infinite loop

D The function should return 'low' instead of 'result'

💡 Hint

Check the loop condition carefully for binary search correctness.

Using 'low < high' can miss checking the last element; 'low <= high' ensures all elements are checked.

🧠 Conceptual

advanced

Why binary search is suitable for finding first and last occurrence?

Why is binary search a good choice to find the first and last occurrence of an element in a sorted array?

A Because it reduces the search space by half each time, making it efficient for sorted arrays

B Because it works only on unsorted arrays and finds all occurrences at once

C Because it uses linear scanning which is faster for large arrays

D Because it modifies the array to bring all occurrences together

💡 Hint

Think about how binary search divides the array.

Binary search halves the search space each step, making it efficient to find positions in sorted arrays.

❓ Predict Output

expert

Output of first and last occurrence in array with all identical elements

What is the output of the code when the array contains all identical elements 7 and we search for 7?

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 main() {
    int arr[] = {7, 7, 7, 7, 7, 7, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 7;
    int first = firstOccurrence(arr, n, x);
    int last = lastOccurrence(arr, n, x);
    printf("First: %d, Last: %d\n", first, last);
    return 0;
}

A First: 1, Last: 5

B First: 3, Last: 3

C First: 0, Last: 6

D First: -1, Last: -1

💡 Hint

All elements are the same, so first is start and last is end index.

Since all elements are 7, first occurrence is at index 0 and last occurrence is at index 6.

Practice

1. What does the term first occurrence of an element in an array mean?

easy

A. The last index where the element appears

B. The total count of the element in the array

C. The index of the first time the element appears in the array

D. The sum of all elements before the element

Solution

1. Step 1: Understand the meaning of first occurrence

   The first occurrence means the earliest position where the element is found in the array, starting from index 0.

2. Step 2: Compare options with definition

   The index of the first time the element appears in the array matches this definition exactly, while others describe different concepts.

3. Final Answer:

   The index of the first time the element appears in the array -> Option C

4. Quick Check:

   First occurrence = first index found [OK]

Hint: First occurrence means earliest index found [OK]

Common Mistakes:

• Confusing first occurrence with count of element
• Mixing first occurrence with last occurrence
• Thinking it means sum or total

2. Which of the following C code snippets correctly finds the first occurrence of x in array arr of size n?

easy

A. for(int i=0; i

B. for(int i=n-1; i>=0; i--) { if(arr[i] == x) return i; } return -1;

C. int i=0; while(arr[i] != x) i++; return i;

D. for(int i=0; i

Solution

1. Step 1: Analyze each code snippet

   for(int i=0; i

2. Step 2: Check other options for correctness

   for(int i=n-1; i>=0; i--) { if(arr[i] == x) return i; } return -1; searches from end, so it finds last occurrence. int i=0; while(arr[i] != x) i++; return i; may cause out-of-bound error if x not found. for(int i=0; i

3. Final Answer:

   for(int i=0; i -> Option A

4. Quick Check:

   Start to end loop with match check = for(int i=0; i

Hint: Loop from start, return index on first match [OK]

Common Mistakes:

• Looping backward for first occurrence
• Not handling element not found case
• Returning wrong index when element differs

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

int arr[] = {2, 4, 6, 4, 8};
int n = 5, x = 4;
int first = -1, last = -1;
for(int i=0; i

medium

A. 1 3

B. 3 1

C. 0 4

D. -1 -1

Solution

1. Step 1: Trace the loop to find first and last occurrence

   Array: [2,4,6,4,8], x=4. Loop i=0 to 4:
   i=0: arr[0]=2 !=4, skip
   i=1: arr[1]=4 ==4, first=-1 so first=1, last=1
   i=2: arr[2]=6 !=4, skip
   i=3: arr[3]=4 ==4, first=1 (unchanged), last=3
   i=4: arr[4]=8 !=4, skip

2. Step 2: Print first and last

   first=1, last=3

3. Final Answer:

   1 3 -> Option A

4. Quick Check:

   First=1, Last=3 indexes for 4 [OK]

Hint: Track first when unset, update last on every match [OK]

Common Mistakes:

• Swapping first and last values
• Not updating last occurrence
• Ignoring first occurrence initialization

4. Identify the error in the following code that tries to find the last occurrence of x in array arr of size n:

int lastOccurrence(int arr[], int n, int x) {
  int last = -1;
  for(int i=0; i

medium

A. Loop should run from n-1 to 0 for last occurrence

B. Using assignment (=) instead of comparison (==) in if condition

C. Variable last should be initialized to 0

D. Return statement should be inside the loop

Solution

1. Step 1: Check the if condition inside the loop

   The condition uses single '=' which is assignment, not comparison. This causes wrong behavior.

2. Step 2: Correct the condition

   It should be 'if(arr[i] == x)' to compare values properly.

3. Final Answer:

   Using assignment (=) instead of comparison (==) in if condition -> Option B

4. Quick Check:

   Use '==' for comparison, not '=' [OK]

Hint: Use '==' for comparison, '=' is assignment [OK]

Common Mistakes:

• Using '=' instead of '==' in conditions
• Loop direction confusion for last occurrence
• Wrong initialization of variables

5. Given a sorted array arr of size n with possible duplicates, which approach is the most efficient to find the first and last occurrence of element x?

hard

A. Sort the array again and then find occurrences

B. Traverse the array from start to end once to find both occurrences

C. Use linear search twice: once from start, once from end

D. Use two binary searches: one for first occurrence, one for last occurrence

Solution

1. Step 1: Understand the array is sorted

   Since the array is sorted, binary search can be used to find positions efficiently.

2. Step 2: Use binary search twice

   One binary search finds the first occurrence by moving left on matches, another finds last occurrence by moving right on matches.

3. Final Answer:

   Use two binary searches: one for first occurrence, one for last occurrence -> Option D

4. Quick Check:

   Sorted array + binary search = fastest method [OK]

Hint: Use binary search twice on sorted array [OK]

Common Mistakes:

• Using linear search on sorted array (slow)
• Sorting array again unnecessarily
• Not using binary search for efficiency