Pair Hunter

Count pairs where char[i] = 'a' and char[j] = 'g' with i < j

Given a character array, count all pairs (i, j) where:

arr[i] = 'a', arr[j] = 'g', and i < j

Brute Force

O(n²)

Carry Forward

O(n)

Pairs Found

Operations

Count of 'g' (Right)

Count of 'g' to the right:

Pairs will appear here...

Check all pairs (i, j) where i < j:

for i = 0 to n-1:
  for j = i+1 to n-1:
    if arr[i]='a' && arr[j]='g':
      count++

Traverse right to left, carry count of 'g':

countG = 0
for i = n-1 to 0:
  if arr[i] = 'g': countG++
  if arr[i] = 'a': pairs += countG