Preface

Min free number puzzle

In the book, we only showed the divide and conqueror method to achieve the linear time O(n), and constant space O(1) solution. There are other ways to achieve such performance. Here are another two.

Before we diving into the detail, let's review the important fact we discussed in the book.

1 <= answer <= n + 1

Where n is the length of the sequence, and the answer is n + 1 when the original sequence is some permutation of 1 to n.

Pigeonhole sort

Any comparison based sort will downgrade the time performance to O(n lg n). So all methods, like heap, BST and so on are out. The idea is that we can put the i-th number x to the position where it should be, the x-th number. When x is greater than n, we know that it cann't be the answer, we can skip it. Otherwise, as the result, we exchange the number at the i-th and the x-th positions. Since the number we swapped to i-th position may not be i, we need repeatedly do this until either it exceeds n, or it becomes i. We iterate i from 1 to n, process all numbers. As each number will only swapped one time, this processing is linear (can you prove it formally?).

Next we scan the array 2nd round, if at any position i, the number isn't i, we find the answer. Otherwise, it means the array is 'full', and we return n+1 as the min free number.

Here is the C-style, C++ code.

int findMinFree1(vector<int> nums) {
    int i, n = nums.size();
    for (i = 0; i < n; ++i)
        while (nums[i] <= n && nums[i] != i + 1)
            swap(nums[i], nums[nums[i] - 1]);
    for (i = 0; i < n; ++i)
        if (i + 1 != nums[i])
            return i + 1;
    return n + 1;
}

Sng encoding

No matter using a flag array, or put the number to its 'right' position, we want to know if a number does exist. Exit or not is a kind of binary information. we can encode it as the sign of the number. The idea is that, if number x exists in the sequence, we mark the x-th number as negative. After we did this marking for all numbers if they are not greater than n, we can scan the sequence from left, find the first positive number. And that position is the answer.

Here is the C-style, C++ code

int findMinFree2(vector<int> nums) {
    int i, k, n = nums.size();
    for (i = 0; i < n; ++i)
        if ((k = abs(nums[i])) <= n)
            nums[k - 1] = - abs(nums[k - 1]);
    for (i = 0; i < n; ++i)
        if (nums[i] > 0)
            return i + 1;
    return n + 1;
}

Missing and Duplicated puzzle

Given numbers from 1 to n, after some processing, there are some changes. 1) The order is shuffled; 2) One number x is mutated to y, here both x, y are from 1 to n. Develop a method to find the x and y in linear time with constant space.

Examples [3, 1, 3, 5, 4] ==> x = 2, y = 3

Divide and Conquer

We can divide the list with the middle number m = floor((1 + n) / 2). Move all the numbers <= m to the left; and the rest to the right.

If the length of left < m, we immediately know that the missing number is on the left. denote s = 1 + 2 + ... + m = m(m + 1)/2, then x = s - sum(left). At the same time, we know that, the duplicated numbers are on the right. Denote s' = (m + 1) + (m + 2) + ... + n = (n + m + 1)(n - m)/2, then y = sum(right) - s';

If the length of left > m, we immediately know that the duplicated number is on the left. Use the similiar method, we have the missign number x = s' - sum(right), and the duplicated number y = sum(left) - s

Otherwise, it means the length of left is equal to m. We know that there are m numbers not greater than m, but we don't know if they are some permutation of 1, 2, ..., m. We can further compare between sum(left) and s. if they are equal, we know the left side is OK, we can drop the whole left side, and recursively find x, y on the right; Otherwise, we drop the right and recursivey find the answer on the left.

During the recursion, we need change 1 in the above discussion to the lower bound of the list. Because each time we halve the list, so the total time, according to the Master Theory, is O(n). Alternatively, we can deduce the time as O(n + n/2 + n/4 + ...) = O(2n) = O(n).

Below are the example code in Haskell and Python.

Haskell divide and conquer example code:

missDup xs = solve xs 1 (toInteger $ length xs) where
  solve xs@(_:_:_) l u | k < m - l + 1 = (sl - sl', sr' - sr)
                       | k > m - l + 1 = (sr - sr', sl' - sl)
                       | sl == sl' = solve bs (m + 1) u
                       | otherwise = solve as l m
      where
          m = (l + u) `div` 2
          (as, bs) = partition (<=m) xs
          k = toInteger $ length as
          sl = (l + m) * (m - l + 1) `div` 2
          sr = (m + 1 + u) * (u - m) `div` 2
          (sl', sr') = (sum as, sum bs)

For Python, if we don't want to generate new lists during partition, we can developed a in-place partition method. It's similar to the N. Lumoto's method in QuickSort.

def partition(xs, l, u, x):
    left = l
    for right in range(l, u):
        if xs[right] < x:
            (xs[left], xs[right]) = (xs[right], xs[left])
            left = left + 1
    return left

def solve_inplace(xs):
    (l, u) = (0, len(xs))
    while l<u:
        m = (l+u)/2
        m1 = partition(xs, l, u, m)
        (nl, nr) = (m1 - l, u - m1);
        (sl, sr) = (sum(xs[l:m1]), sum(xs[m1:u]))
        sl1 = (l + m - 1)*(m - l)/2
        sr1 = (m + u - 1)*(u - m)/2
        if m1 < m:
            return (sl1 - sl, sr - sr1)
        elif m1 > m:
            return (sr1 - sr, sl - sl1)
        else:
            if sl == sl1:
                l = m1
            else:
                u = m1

Here is the scala example: https://github.com/liuxinyu95/AlgoXY/blob/algoxy/others/problems/miss-dup/MissDup.scala

End