Условие задачи:
Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно
число в этом массиве повторяется два раза. Найти это число за время O(N).

Реализация:

private static string separator = ";";
        static void Main(string[] args)
        {
            int[] result = GetIntArray(InputArray());
            PrintArray(result);
            Console.WriteLine(ff(result));
            Console.ReadLine();
        }
        private static string InputArray()
        {
            Console.WriteLine("Введите массив, содержащий только целые числа.");
            Console.WriteLine("После каждого числа ставьте разделитель '{0}'", separator);
            Console.WriteLine("Введите массив: ");
            return Console.In.ReadLine();
        }
        private static int[] GetIntArray(string insert)
        {
            string pattern = String.Format("{0}(?=(?:[^\"]*\"[^\"]*\")*(?![^\"]*\"))", separator);
            string[] bufResult = Regex.Split(insert, pattern);
            int[] result = new int[bufResult.Length];
            for (int i = 0; i < bufResult.Length; i++)
            {
                result[i] = Int32.Parse(bufResult[i]);
            }
            return result;
        }
        private static void PrintArray(int[] array)
        {
            foreach(int i in array)
            {
                Console.WriteLine(i);
            }
        }
        private static int ff(int[] array)
        {
            int m = 1;
            int buf = 0;
            // общее количество сравнений (n-1)^2, где n - длина массива
            for (int i = 0; i < (array.Length - 1) * (array.Length - 1); i++)
            {
                // количество перестановок (n-1) = количеству сравнений array[0] и array[k], где k - числа от 1 до n (n - длина массива)
                for (int j = 1; j < array.Length; j++)
                {
                    if (array[0] == array[j])
                    {
                        buf = array[0];
                        goto result;
                    }
                }
                Swap(array, m);
                m++;
            }
        result:
        return buf;
        }
        private static void Swap(int[] array, int index)
        {
            int temp = array[index];
            array[index] = array[0];
            array[0] = temp;
        }

Есть ли какие-либо другие пути решения задачи? Без goto не вижу решения задачи, если использовать break, там где buf = array[0] , останавливается только цикл:

for (int j = 1; j < array.Length - 1; j++)

при этом работа цикла

for (int i = 0; i < (array.Length - 1) * (array.Length - 1); i++)

не прерывается

Заранее спасибо!