Last Updated: 21 Aug, 2021
Take Away The Bottle
Hard
Asked in company
There is a row of numbered bottles, and now you need to take them all away. You can only take several consecutive bottles at a time, and you need to make sure that the bottle number is a palindrome string.
Palindrome string refers to the same string read in both forward and reverse directions
For example:
“4664” when read forward and backward will give the same result. Hence it is a palindrome.
Your task is to find the minimum number of times it takes to remove all bottles.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows.
The first line of each test case contains an integer ‘N’, denoting the number of bottles.
The second line of each test case contains ‘N’ space-separated integers.
Output Format :
For each test case, print the minimum number of times it takes to remove all bottles.
Output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 <= N <= 500
1<= bottles[i] <= 1000
Time limit: 1 sec
Approaches
Let’s take two pointers, i and j. I is initialized to 0 and j is initialized to N - 1.
Now if bottle[i] == bottle[i + 1]
- Then we have two choices,
- Either take both these bottles as a palindrome (since they are equal) and recursively call for this range (i + 2,j)
- Take only the first bottle, and recursively call for this range (i + 1,j) (since it may happen that bottle[i +1] is forming a longer palindrome with other bottles.
- Now we know that each bottle is a palindrome in itself (all 1 digit numbers are palindrome) so we will take them, and recursively call for rest of the parts,
- For example, if I take a bottle at index ‘k’, then I will call on (i,k - 1) and (k + 1,j)
- Ultimately update our answer accordingly whenever we find a value less than current ans.
- Otherwise, if bottle[i] != bottle[i+1] then
- We only have one option to take the starting bottle and recursively call on (i+1,j).
- After that, we will call recursion on the rest of the bottles,
- For example, if i take a bottle at index ‘k’, then i will call on (i,k - 1) and (k + 1,j)
This approach is similar to the previous approach, but here we are saving the answers in a 2-D DP array.
Since we have initially taken 2-pointers i and j, and all our recursive calls fall under the range of [i,j], it gives us an idea that all the answers to the recursive calls can be stored under a grid of size ‘N’ * ’N’ where ‘N’ is the number of bottles, Due to the fact that maximum values of i and j are ‘N’ only.
Here DP of (i,j) indicates the minimum possible answers in between the range of [i,j].
Now if bottle[i] == bottle[i + 1]
- Then we have two choices,
- Either take both these bottles as a palindrome (since they are equal) and recursively call for this range (i+2,j)
- Save the answer to these calls in a DP array.
- Take only the first bottle, and recursively call for this range (i+1,j) (since it may happen that bottle[i+1] is forming a longer palindrome with other bottles.
- Now we know that each bottle is a palindrome in itself (all 1 digit numbers are palindrome) so we will take them, and recursively call for the rest of the parts,
- For example, if i take a bottle at index ‘k’, then i will call on (i,k-1) and (k+1,j)
- Finally, we will update our answer if the value of the current minimum is less than our current answer. Then we also have to save this answer in our DP array.
- Otherwise, if bottle[i] != bottle[i + 1] then
- We only have one option to take the starting bottle and recursively call on (i + 1,j).
- After that, call recursion on the rest of the bottles,
- For example, if i take a bottle at index ‘k’, then i will call on (i,k - 1) and (k + 1,j)
- Finally, we will update our answer if the value of the current minimum is less than our current answer. Then we also have to save this answer in our DP array.
Similar problems