IAE Academy

GATE 2025 CS1 Q.61: solution and answer

GATE 2025 · CS1Q.61 · 2 marks · NAT
#include <stdio.h>
int foo(int S[],int size){
    if(size == 0) return 0;
    if(size == 1) return 1;
    if(S[0] != S[1]) return 1+foo(S+1,size-1);
    return foo(S+1,size-1);
}
int main(){
    int A[]={0,1,2,2,2,0,0,1,1};
    printf("%d",foo(A,9));
    return 0;
}

The value printed by the given C program is _______ . (Answer in integer)

See the question in the paper
GATE 2025 CS1 question 61Tap to open full size

Answer and solution

ANSWER

The value printed by the program is 5.

Official answer: 5Source: Official answer key, GATE 2025 CS1 (IIT Roorkee)

  1. Array A[0..8] = {0,1,2,2,2,0,0,1,1}, so foo is called as foo(A,9).

  2. The recursion compares consecutive elements: while the current pair of adjacent elements (S[0] and S[1]) differ, it counts 1 and recurses on the rest of the array; while they are equal, it recurses without counting (skips one duplicate).

  3. foo(A,9): A[0]=0, A[1]=1, different → 1 + foo(A+1,8)

  4. foo(A+1,8) (window A[1..8] = 1,2,2,2,0,0,1,1): A[1]=1, A[2]=2, different → 1 + foo(A+2,7)

  5. foo(A+2,7) (window A[2..8] = 2,2,2,0,0,1,1): A[2]=2, A[3]=2, equal → foo(A+3,6)

  6. foo(A+3,6) (window A[3..8] = 2,2,0,0,1,1): A[3]=2, A[4]=2, equal → foo(A+4,5)

  7. foo(A+4,5) (window A[4..8] = 2,0,0,1,1): A[4]=2, A[5]=0, different → 1 + foo(A+5,4)

  8. foo(A+5,4) (window A[5..8] = 0,0,1,1): A[5]=0, A[6]=0, equal → foo(A+6,3)

  9. foo(A+6,3) (window A[6..8] = 0,1,1): A[6]=0, A[7]=1, different → 1 + foo(A+7,2)

  10. foo(A+7,2) (window A[7..8] = 1,1): A[7]=1, A[8]=1, equal → foo(A+8,1)

  11. foo(A+8,1): base case size==1 → returns 1

  12. Unwinding: foo(A+7,2) = 1; foo(A+6,3) = 1+1 = 2; foo(A+5,4) = 2; foo(A+4,5) = 1+2 = 3; foo(A+3,6) = 3; foo(A+2,7) = 3; foo(A+1,8) = 1+3 = 4; foo(A,9) = 1+4 = 5

  13. The program prints 5.

KEY IDEA

The function walks the array with a "current index / remaining size" recursion, adding 1 whenever the current element differs from the next one and skipping the count (just recursing on the smaller window) whenever it matches — effectively counting "boundaries" between unequal adjacent elements while chaining through a run of equal ones, until only one element (or zero) is left.

WATCH OUT FOR

Losing track of which two elements are being compared at each recursive call (since the array pointer shifts by one each time but the comparison is always between the first two elements of the current window, i.e. positions i and i+1 of the original array), or forgetting that a "match" case still advances the pointer by one without adding to the count — leading to either double-counting or missing a boundary.

From the GATE 2025 CS1 paper. Every question of this paper · Download the full paper · All 9 Recursion questions, with notes

More Recursion questions