GATE CSE 2016 | Set 2 | Question: 37

Question

Consider the following program:

int f (int * p, int n) 
{ 
    if (n <= 1) return 0; 
    else return max (f (p+1, n-1), p[0] - p[1]); 
}
 int main () 
{
    int a[] = {3, 5, 2, 6, 4}; 
    printf(" %d", f(a, 5)); 
}

Note: $\max (x, y)$ returns the maximum of $x$ and $y$.

The value printed by this program is ________.

Comments

Try this in http://pythontutor.com

-------------------------------------------------------

int f (int * p, int n)
{
 if (n <= 1) return 0;
 else 
 return f(p+1, n-1)>(p[0] - p[1])?f (p+1, n-1):(p[0] - p[1]);
}
int main ()
{
 int a[] = {3, 5, 2, 6, 4};
 printf(" %d", f(a, 5));
}

---

@arjun sir, I think there is some typo. It will be printf() in main() instead of print f.

As f is also a function is its bit confusing

---

https://www.youtube.com/watch?v=h1ds9EuyWmU

---

For an intutive understanding of the code, focus on the return statement of the function f. The function returns the maximum value between two expressions: the result of the recursive call and the difference between the first two elements of the array.

As the recursion unfolds, each call evaluates the difference between adjacent elements and compares it with the recursively computed maximum difference. This process continues until all pairs of consecutive elements have been examined. Ultimately, the function computes the maximum difference among all the adjacent pairs, i.e., $\text{max}(a[i] - a[i+1])$, across the entire array.

Answer 1

$f(a,5)$

• $p$ , $n=5.$ $\begin{array}{|l|l|l|l|l|} \hline 3 & 5 & 2 &  6 &   4 \\\hline \end{array}$
  $\max(f(p+1,5-1),3-5) = \max(f(p+1,4),-2)$
• $p$ , $n=4. \begin{array}{|l|l|l|l|} \hline 5 & 2 &  6 &   4 \\\hline \end{array}$
  $\max(\max(f(p+1,4-1),5-2),-2)=\max(\max(f(p+1,3),3),-2)$
• $p$ , $n=3. \begin{array}{|l|l|l|} \hline 2 &  6 &   4 \\\hline \end{array}$
  $\max(\max(\max(f(p+1,3-1),2-6),3),-2) =\max(\max(\max(f(p+1,2),-4),3),-2)$
• $p$ , $n=2.\begin{array}{|l|l|} \hline 6 &   4 \\\hline \end{array}$
  $\max(\max(\max(\max(f(p+1),1),2),-4),3),-2)$
• $n=1$, return $0$

$\max(\max(\max(\max(0,2),-4),3),-2)$

$=\max(\max(\max(2,-4),3),-2)$

$=\max(\max(2,3),-2)$

$=\max(3,-2)$

$=3$

Comments

Can anyone tell me what this function do actually??

---

@MRINMOY_HALDER  find the maximum difference if two subsequent array elements are subtracted .

---

post increment bro

Answer 2

Ans is 3

Comments

Can you please explain the reason behind the increment of Index in p[0] and p[1].

---

@asifalam Firstly p+1 does not mean incrementing of p, instead p+1 is passed as parameter to p of function.

But p[0]=3 p[1]=5

 

---

Okk when p+1 passed as parameter it act as new pointer again just like we are again setting the new pointer from a+1?

Answer 3

It can easily be solved by observing the code.

Here in the code they are trying to figure out max(array[i]-array[i-1])

so answer will be max(a[0]-a[1],a[1]-a[2],a[2]-a[3],a[3]-a[4])

                          = max(3-5,5-2,2-6,6-4)

                         = max(-2,3,-4,2)

                         = 3

Answer 4

Answer : 3

 

Comments

how 6-4=-2 in last

 

---

@mayanksinghchandel Thanks for pointing it out. I’ve corrected it now.

 

Answer 5

solution is given below:-

Answer 6

Using recursion tree method