GATE Overflow Test Series | Mock GATE | Test 5 | Question: 45

Question

Consider the following C program:

#include <stdio.h>
int foo(int A[], int n, int s)
{
    for (int i = 0; i < n - 2; i++) 
        for (int j = i + 1; j < n - 1; j++) 
            for (int k = j + 1; k < n; k++)
                if (A[i] + A[j] + A[k] == s)
                    return i+j+k+3;
    return 0;
}
int main()
{
    int A[] = { 6, 14, 15, 3, 1, 10, 10 };
    int n = sizeof(A) / sizeof(A[0]);
    printf("%d", foo(A, n, 24));
    return 0;
}

If the output of the above code is $x$ and the time complexity of the function $\text{foo}$ is $\Theta(n^k)$ where $n$ is the number of elements in the array passed to it (second argument), then $x+ k = $ ________

Answer 1

The given function is returning the indices (from 1) of the first occurrence of three elements such that they sum to $24.$  Here, it happens for  $6+15+3$ which are at positions $1,3$ and $4.$ So, the return value of the function $=1+3+4 = 8.$

The time complexity of the function is $\Theta(n^3)$ and so $k = 3.$

Thus, $x+ k = 8+3=11.$

Comments

@gatecse Why indexing is considered from 1 ?

shouldn't i=0, j=2, k=3 instead of i=1,j=3, k=4?

---

Yes, but that's why +3 is there in return.

---

and after a correct analysis that +3 might lead to a silly mistake!