/ #algorithms 

Find Duplicates Algorithm

Find Duplicates

Solution to the “Find Duplicates” problem in C#

Problem

Given an array of n elements which contains elements from 0 to n-1, with any of these numbers appearing any number of times. Find these repeating numbers in O(n) and using only constant memory space.

Check the complete project on my Github

Example

Input:

[1, 4, 3, 1, 4, 4, 8]

Output:

1 4 4

Algorithm

  • Iterate over the array from 0 to n - 1 elements.
  • Check for the sign of array[abs[array[i]]]
  • If positive (+) then
  • Make it negative (-) by array[abs[array[i]]] = - array[abs[array[i]]]
  • Else // i.e., A[abs(A[i])] is negative
  • This element (ith element of the array) is a repetition

Solution

using System;
namespace FindDuplicates
{
    class Program
    {
        public static void FindDuplicates(int[] arr, int size)
        {
            for (var i = 0; i < size-1; i++)
            {                
                if (arr[Math.Abs(arr[i])] >= 0)
                {
                    arr[Math.Abs(arr[i])] = -arr[Math.Abs(arr[i])];                  
                }
                else
                {
                    Console.Write(Math.Abs(arr[i]));
                }          
            }
        }
        static void Main(string[] args)
        {
            int[] arr = {1, 4, 3, 1, 4, 4, 8};
            int size = arr.Length;
            FindDuplicates(arr, size);
            Console.ReadLine();
        }
    }
}
Author

Abraham Laria

Sr. Software Engineer at Pinnacle Entertainment Inc. Aspiring Solution Architect, interested in Team Management.