Last remaining number

Question

I was asked this question in an interview.

Given an array 'arr' of positive integers and a starting index 'k' of the array. Delete element at k and jump arr[k] steps in the array in circular fashion. Do this repeatedly until only one element remain. Find the last remaining element.

I thought of O(nlogn) solution using ordered map. Is any O(n) solution possible?

Answer 1

My guess is that there is not an O(n) solution to this problem based on the fact that it seems to involve doing something that is impossible. The obvious thing you would need to solve this problem in linear time is a data structure like an array that exposes two operations on an ordered collection of values:

1. O(1) order-preserving deletes from the data structure.
2. O(1) lookups of the nth undeleted item in the data structure.

However, such a data structure has been formally proven to not exist; see "Optimal Algorithms for List Indexing and Subset Rank" and its citations. It is not a proof to say that if the natural way to solve some problem involves using a data structure that is impossible, the problem itself is probably impossible, but such an intuition is often correct.

Anyway there are lots of ways to do this in O(n log n). Below is an implementation of maintaining a tree of undeleted ranges in the array. GetIndex() below returns an index into the original array given a zero-based index into the array if items had been deleted from it. Such a tree is not self-balancing so will have O(n) operations in the worst case but in the average case Delete and GetIndex will be O(log n).

namespace CircleGame
{
    class Program
    {
        class ArrayDeletes
        {
            private class UndeletedRange
            {
                private int _size;
                private int _index;
                private UndeletedRange _left;
                private UndeletedRange _right;

                public UndeletedRange(int i, int sz)
                {
                    _index = i;
                    _size = sz;
                }

                public bool IsLeaf()
                {
                    return _left == null && _right == null;
                }

                public int Size()
                {
                    return _size;
                }

                public void Delete(int i)
                {
                    if (i >= _size)
                        throw new IndexOutOfRangeException();

                    if (! IsLeaf())
                    {
                        int left_range = _left._size;
                        if (i < left_range)
                            _left.Delete(i);
                        else
                            _right.Delete(i - left_range);
                        _size--;
                        return;
                    }

                    if (i == _size - 1)
                    {
                        _size--; // Can delete the last item in a range by decremnting its size
                        return;
                    }

                    if (i == 0)  // Can delete the first item in a range by incrementing the index
                    {  
                        _index++;
                        _size--;
                        return;
                    }

                    _left = new UndeletedRange(_index, i);
                    int right_index = i + 1;
                    _right = new UndeletedRange(_index + right_index, _size - right_index);
                    _size--;
                    _index = -1; // the index field of a non-leaf is no longer necessarily valid.
                }

                public int GetIndex(int i)
                {
                    if (i >= _size)
                        throw new IndexOutOfRangeException();

                    if (IsLeaf())
                        return _index + i;

                    int left_range = _left._size;
                    if (i < left_range)
                        return _left.GetIndex(i);
                    else
                        return _right.GetIndex(i - left_range);
                }

            }

            private UndeletedRange _root;

            public ArrayDeletes(int n)
            {
                _root = new UndeletedRange(0, n);
            }

            public void Delete(int i)
            {
                _root.Delete(i);
            }

            public int GetIndex(int indexRelativeToDeletes )
            {
                return _root.GetIndex(indexRelativeToDeletes);
            }

            public int Size()
            {
                return _root.Size();
            }
        }

        static int CircleGame( int[] array, int k )
        {
            var ary_deletes = new ArrayDeletes(array.Length);
            while (ary_deletes.Size() > 1)
            {
                int next_step = array[ary_deletes.GetIndex(k)];
                ary_deletes.Delete(k);
                k = (k + next_step - 1) % ary_deletes.Size();
            }
            return array[ary_deletes.GetIndex(0)];
        }

        static void Main(string[] args)
        {
            var array = new int[] { 5,4,3,2,1 };
            int last_remaining = CircleGame(array, 2); // third element, this call is zero-based...
        }
    }
}

Also note that if the values in the array are known to be bounded such that they are always less than some m less than n, there are lots of O(nm) algorithms -- for example, just using a circular linked list.