Finding duplicate number in a Sequence

05 Jun 2016

Finding the duplicate in a sorted sequence of integer is a frequently asked interview question. This can be solved in a couple of ways, that are explained in the below article.

Method 1:

Comparison of adjacent numbers:

This is a simple solution, that involves

  1. comparison of adjacent elements in the given array.
  2. The difference between adjacent elements should be 1 otherwise output as a duplicate number
public int FindDuplicateNumber(int[] numbers)
{
    for (int i = 1; i < numbers.Length; i++)
        if (numbers[i] - numbers[i - 1] != 1)
            return (numbers[i];
    return 0;
}

The time complexity for above linear comparison algorithm is O(n). but the following is more effective than this.

Method 2:

Finding the duplicated number using Binary Search method.:

Binary search algorithm works based on Divide and Conquer strategy. The given sorted list of integers will be divided into two sets and the set which has the possibility of containing the duplicated element is chosen as the input sample for the next iteration. There by the number of elements to compare almost reduces by 2 at the end of each iteration.

The main decision making parameter for this problem is : whether there is any discrepancy in the left half of the set (i.e., whether the mid value is as expected) ? IF NOT, then the required number should be in the right half. This continues till the algorithm narrows it to a particular number.

For sake of easy understanding and coding, we always try to write the Binary search and do the comparisons against the array index rather than the actual array values. Then initial offset between first element and 1 is only taken into consideration, while comparing against the array value and also before returning the result.

namespace CodeSamples
{
    using static System.Console;
    class DuplicateNumberBinarySearch
    {
        public static int? FindDuplicateNumber(int[] numbers)
        {
            int low = 0, high = numbers.Length - 1, mid = 0;
            int offsetValue = numbers[low] - 1;

            while (low <= high)
            {
                mid = (low + high) / 2;

                if (offsetValue + mid == numbers[mid] - 1)
                    low = mid + 1;
                else
                    high = mid - 1;
            }
            //If there is no duplicated number
            if (numbers.Length + offsetValue == high + offsetValue + 1)
                return null;
            //Else return the last resolved number as duplicate
            return high + offsetValue + 1;
        }

        public static void Main(string[] args)
        {
            int[] numbers = new int[] { -4, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5 };
            WriteLine(FindDuplicateNumber(numbers));

            numbers = new int[] { 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
            WriteLine(FindDuplicateNumber(numbers));

            numbers = new int[] { 1, 2, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
            WriteLine(FindDuplicateNumber(numbers));

            numbers = new int[] { 1, 2, 3, 3, 4, 5, 6, 7, 8, 9, 10 };
            WriteLine(FindDuplicateNumber(numbers));

            numbers = new int[] { 1, 2, 3, 4, 4, 5, 6, 7, 8, 9, 10 };
            WriteLine(FindDuplicateNumber(numbers));

            numbers = new int[] { 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 10 };
            WriteLine(FindDuplicateNumber(numbers));

            numbers = new int[] { 1, 2, 3, 4, 5, 6, 6, 7, 8, 9, 10 };
            WriteLine(FindDuplicateNumber(numbers));

            numbers = new int[] { 1, 2, 3, 4, 5, 6, 7, 7, 8, 9, 10 };
            WriteLine(FindDuplicateNumber(numbers));

            numbers = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 10 };
            WriteLine(FindDuplicateNumber(numbers));

            numbers = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 10 };
            WriteLine(FindDuplicateNumber(numbers));

            numbers = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10 };
            WriteLine(FindDuplicateNumber(numbers));

            numbers = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
            WriteLine(FindDuplicateNumber(numbers));

            numbers = new int[] { 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 11 };
            WriteLine(FindDuplicateNumber(numbers));
        }
    }
}

The time complexity for above algorithm is O(log n).

Hope this is helpful. Share your thoughts or ideas for solving this much efficiently.