Please read the new rule regarding the restriction on the use of AI tools. ×

gaand_na_phulao's blog

Minimum number of student remaining
By gaand_na_phulao, history, 4 years ago, In English

Yesterday I had a Samsung test. There a question which I wasn't able to solve. Can someone please tell me how to solve this. (Sorry for my bad English and also I can't provide the link for exact question).

You have given n student. Each student contains a number ( which need not be unique). Students are standing in a queue. You have also given an integer k. You can remove the students such that the number contains by students follow this rule:

  • $$$ arr[i-1]+k=arr[i]=arr[i+1]-k $$$.(All three students will be removed from the queue).

You have to remove these students such that the minimum number of student will be remaining at the end.

Constraints:

  • $$$ 1<=t<=20. $$$

  • $$$ 3<=n<=100. $$$

  • $$$ 1<=k<=10^6 $$$.

  • $$$ 1<=arr[i]<=10^6 $$$.

Input :

2

6 1

3 4 5 6 7 5

5 1

1 2 3 4 5

Output:

0

2

Explanation: In the first test case, If we remove 5 6 7 then the remaining array will be 3 4 5. Now again I can remove these students. So the minimum number of student remaining will be 0.

In the second test case, we can't remove more than three students from the queue. So the remaining number of students will be 2.

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

I solved it by using DP. DP[s][e] is storing maximum no of student you can remove between s and e.

Hint
→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    While removing a[i], a[i+1] and a[j] shouldn't we check if dp[i+2][j-1] == j-i-2. That is, all elements from [i+2,j-1] should get removed if we want to club i,i+1 and j together.

    Moreover, while considering dp[i][j], we should iterate over intervals of length 3,

    [k,k+2] for k>=i && k+2<=j signifying that we try to remove them first.

    Please, can anybody confirm the correctness of these two claims?

    → Reply