Compress the Video solution codechef

Compress the Video solution codechef

Chef recorded a video explaining his favorite recipe. However, the size of the video is too large to upload on the internet. He wants to compress the video so that it has the minimum size possible.

Chef’s video has NN frames initially. The value of the ithith frame is AiAi. Chef can do the following type of operation:

  • Choose an index ii (1iN)(1≤i≤N) such that the value of the ithith frame is equal to the value of either of its neighbors and remove the ithith frame.

Find the minimum number of frames Chef can achieve.

Input Format

Compress the Video solution codechef

  • First line will contain TT, the number of test cases. Then the test cases follow.
  • The first line of each test case contains a single integer NN – the number of frames initially.
  • The second line contains NN space-separated integers, A1,A2,,ANA1,A2,…,AN – the values of the frames.

Output Format

For each test case, output in a single line the minimum number of frames Chef can achieve.

Constraints

Compress the Video solution codechef

  • 1T10001≤T≤1000
  • 1N1051≤N≤105
  • 1Ai1061≤Ai≤106
  • Sum of NN over all test cases does not exceed 21052⋅105.

Sample Input 1 

4
1
5
2
1 1
3
1 2 3
4
2 1 2 2

Sample Output 1

Compress the Video solution codechef

1
1
3
3

Explanation

Compress the Video solution codechef

Test case 11: There is only one frame with value 55. Since there are no neighbors, Chef won’t remove any frame and the minimum number of frames Chef can achieve is 11.

CodeChef was created as a platform to help programmers make it big in the world of algorithms, computer programming and programming contests. At CodeChef, we work hard to revive the geek in you by hosting a programming contest at the start of the month and another smaller programming challenge in the middle of the month.

Test case 22: There are two frames where both frames have value 11. Chef can remove the first frame as the value of the first frame is equal to that of the second frame. The remaining frames have values [1][1]. The minimum number of frames Chef can achieve is 11.

Test case 33: There are 33 frames. All frames have distinct values. Thus, the minimum number of frames Chef can achieve is 33.

Test case 44: Chef can remove the fourth frame as the value of the fourth frame is equal to that of the third frame. The remaining frames have values [2,1,2][2,1,2]. Thus, the minimum number of frames Chef can achieve is 33.

SOLUTION

Click here

Compress the Video solution codechef is one of the most asked coding question. This question is repeated in almost every company paper and if you are ready to crack the interviews and the question papers then you must check our website on daily purpose so that you can get the answer of the latest question “Compress the Video solution codechef”.

Leave a Comment