# What will be the recursive solution for this

I know it’s embarrassing to ask such a easy question.
But what will be the recursive solution for this question.
https://codeforces.com/contest/253/problem/B

My approach:

`````` static int dir(int[] a, int i, int j) {
int s = 2 * a[i] - a[j];
if (s >= 0)
return 0;
else
return min((1 + dir(a, ++i, j),(1 + dir(a, i, --j));
}
``````

What is wrong with this solution?

Lets try this, I will make you realize the error yourself.

• What does dir do? What does this function represent to you?
• Is it dp if we are not storing states?
• What is my state in dp? By state I mean variables (and their meaning/what-they-represent).
• What is my transition? If you are at a state what next states you can go to?
1 Like

I have not memoize this solution as of now. Array ‘a’ is already, I have taken two pointers one pointing at last index and other at 0 index, as array is already sorted j index will be pointing to greatest element and i index will be pointing to first index
so for every index we have choice whether to take ‘i’ index element as smallest or not, if not I increments the i by +1 this goes for ‘j’ index as well.
In a way I’m trying all the combinations.

In this TC -

10

39 9 18 13 6 16 47 15 1 24

the o/p is 5

But my approach return 3

I get your approach, that you sort the array and then play with 2 pointers.

BTW - `return min((1 + dir(a, ++i, j)) + (1 + dir(a, i, --j)));` I believe it should be a comma instead of plus? What min function is this that it accepts just one argument? XD

• What are states?

• The variables i,j represent state. i will point to the current minimum element we can discard, j points to current maximum element we can discard. Hence, my state has 2 independent variables (i,j). With this in mind, dp[i][j] will represent the solution for subarray [i,j].
• What are my transitions?

• I can either discard either the element at i or the element at j. So my next states can be (i+1,j) or (i,j-1).
• So that makes the transitions correct as well, as we will take the one providing minimum value to answer.

I think its that min typo maybe. Can you share your full code?

1 Like

Yes that’s what I mean, it’s so stupid of me of not checking what I’m writing.
This is exactly my code is doing.

This is the full code

``````    import java.util.*;
import java.io.*;

class Test {
static int dir(int[] a, int i, int j) {
int s = 2 * a[i] - a[j];
if (s >= 0)
return 0;
else
return Math.min((1 + dir(a, ++i, j)), (1 + dir(a, i, --j)));
}

public static void main(String[] args) throws IOException {
//        Scanner input = new Scanner(new File("input.txt"));
//        PrintWriter out = new PrintWriter(new File("output.txt"));
Scanner sc = new Scanner(System.in);

int n = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < a.length; i++) {
a[i] = sc.nextInt();
}
Arrays.sort(a);
int x = (2 * a - a[n - 1]);
System.out.println(dir(a, 0, n - 1));
}``````

In your code, look at -

`return Math.min((1 + dir(a, ++i, j)), (1 + dir(a, i, --j)));`

Change the `++i` to `i+1` and similarly for j, because if you use ++i, the i for next function call also gets incremented. Meaning, after the ++i in first dir call, the i in second dir call is actually i+1.

4 Likes I’m dumb.