GATE CS 2011 Q49 — Algorithm Design: Dynamic Programming

Consider the following recursive C function that takes two arguments.

unsigned int foo(unsigned int n, unsigned int r) {
    if (n>0) return ((n%r) + foo(n/r, r));
    else return 0;
}

What is the return value of the function $\text{foo}$ when it is called as $\text{foo(513, 2)}$ ?

View worked solution

Answer: D

The given recursive function foo(n, r) computes the sum of the digits of the number $n$ when represented in base $r$ .

n % r extracts the least significant digit of $n$ in base $r$ .
n / r performs an integer division, effectively shifting $n$ to the right by one digit in base $r$ .
The recursion terminates when $n = 0$ , returning $0$ .

Therefore, foo(n, r) returns the sum of the digits of $n$ in base $r$ .

Here, $n = 513$ and $r = 2$ (binary representation).

We express $513$ in binary (base 2):

513 = 512 + 1 = 2^9 + 2^0 = (1000000001)_2

The sum of the binary digits (the number of set bits) is:

1 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 1 = 2

Thus, the function returns 2.

Free practice · Your answers on this page are not saved.

Published 10 Oct 2026

Related questions