Take Away The Bottle

Hard
0/120
profile
Contributed by
10 upvotes
Asked in company
Microsoft

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
5
1 3 4 1 5
3
4 6 4
Sample Output 1 :
3
1
Explanation For Sample Output 1 :
For test case 1 :
We can take bottle number 4, then the bottle array will be: 1 3 1 5

Then we can take 1 3 1 at the same time since it is a palindrome and the array will be: 5
Then we will take bottle number 5

For test case 2 :
We can take all the bottles at once since they form a palindrome

Sample Input 2 :

2
6
1 2 3 5 3 1
6
1 1 2 3 1 1
Sample Output 2 :
2
2
Hint

Try to find all possible combinations of what will happen if a particular bottle gets removed.

Approaches (2)
Recursion

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)
Time Complexity

O( N! ), where ‘N’ is the number of bottles.

 

Since we are calling in each interval, and then each interval will call in its sub-interval. It will lead to an exponential number of calls, hence complexity is exponential.

Space Complexity

O( 1 )

 

As we have not used any extra space.

Code Solution
(100% EXP penalty)
Take Away The Bottle
Full screen
Console