Minimum Delete operations to empty the vector

Admin 1
Viewed 228

My friend was asked this question in an interview:

We have a vector of integers consisting only of 0s and 1s. A delete consists of selecting consecutive equal numbers and removing them. The remaining parts are then attached to each other. For e.g., if the vector is [0,1,1,0] then after removing [1,1] we get [0,0]. We need one delete to remove an element from the vector, if no consecutive elements are found.

We need to write a function that returns the minimum number of deletes to make the vector empty.

Examples 1:

Input: [0,1,1,0]

Output: 2

Explanation: [0,1,1,0] -> [0,0] -> []

Examples 2:

Input: [1,0,1,0]

Output: 3

Explanation: [1,0,1,0] -> [0,1,0] -> [0,0] -> [].

Examples 3:

Input: [1,1,1]

Output: 1

Explanation: [1,1,1] -> []

I am unsure of how to solve this question. I feel that we can use a greedy approach:

  1. Remove all consecutive equal elements and increment the delete counter for each;
  2. Remove elements of the form <a, b, c> where a==c and a!=b, because of we had multiple consecutive bs, it would have been deleted in step (1) above. Increment the delete counter once as we delete one b.
  3. Repeat steps (1) and (2) as long as we can.
  4. Increment delete counter once for each of the remaining elements in the vector.

But I am not sure if this would work. Could someone please confirm if this is the right approach? If not, how do we solve this?

algorithm
2 Answers

Hint

You can simplify this problem greatly by noticing the following fact: a chain of consecutive zeros or ones can be shortened or lengthened without changing the final solution. By example, the two vectors have the same solution:

[1, 0, 1]
[1, 0, 0, 0, 0, 0, 0, 1]

With that in mind, the solution becomes simpler. So I encourage you to pause and try to figure it out!

Solution

With the previous remark, we can reduce the problem to vectors of alternating zeros and ones. In fact, since zero and one have no special meaning here, it suffices to solve for all such vector which start by... say a one.

[]                        # number of steps: 0
[1]                       # number of steps: 1
[1, 0]                    # number of steps: 2
[1, 0, 1]                 # number of steps: 2
[1, 0, 1, 0]              # number of steps: 3
[1, 0, 1, 0, 1]           # number of steps: 3
[1, 0, 1, 0, 1, 0]        # number of steps: 4
[1, 0, 1, 0, 1, 0, 1]     # number of steps: 4

We notice a pattern, the solution seems to be floor(n / 2) + 1 for n > 1 where n is the length of those sequences. But can we prove it..?

Proof

We will proceed by induction. Suppose you have a solution for a vector of length n - 2, then any move you do (except for deleting the two characters on the edges of the vector) will have the following result.

[..., 0, 1, 0, 1, 0 ...]
            ^------------ delete this one

Result:
[..., 0, 1, 1, 0, ...]

But we already mentioned that a chain of consecutive zeros or ones can be shortened or lengthened without changing the final solution. So the result of the deletion is in fact equivalent to now having to solve for:

[..., 0, 1, 0, ...]

What we did is one deletion in n elements and arrived to a case which is equivalent to having to solve for n - 2 elements. So the solution for a vector of size n is...

Solution(n) = Solution(n - 2) + 1
           = [floor((n - 2)  / 2) + 1] + 1
           = floor(n / 2) + 1

Keeping in mind that the solutions for [1] and [1, 0] are respectively 1 and 2, this concludes our proof. Notice here, that [] turns out to be an edge case.

Interestingly enough, this proof also shows us that the optimal sequence of deletions for a given vector is highly non-unique. You can simply delete any block of ones or zeros, except for the first and last ones, and you will end up with an optimal solution.

Conclusion

In conclusion, given an arbitrary vector of ones and zeros, the smallest number of deletions you will need can be computed by counting the number of groups of consecutive ones or zeros. The answer is then floor(n / 2) + 1 for n > 1.

Just for fun, here is a Python implementation to solve this problem.

from itertools import groupby

def solution(vector):
    n = 0
    for group in groupby(vector):
        n += 1

    return n // 2 + 1 if n > 1 else n
user_50793160

Intuition: If we remove the subsegments of one integer, then all the remaining integers are of one type leads to only one operation.

Choosing the integer which is not the starting one to remove subsegments leads to optimal results.

Solution:

Take the integer other than the one that is starting as a flag.

Count the number of contiguous segments of the flag in a vector.

The answer will be the above count + 1(one operation for removing a segment of starting integer)

So, the answer is:

answer = Count of contiguous segments of flag + 1

Example 1:

[0,1,1,0]

flag = 1

Count of subsegments with flag = 1

So, answer = 1 + 1 = 2

Example 2:

[1,0,1,0]

flag = 0

Count of subsegments with flag = 2

So, answer = 2 + 1 = 3

Example 3:

[1,1,1]

flag = 0

Count of subsegments with flag = 0

So, answer = 0 + 1 = 1

user_136519780
Related