using System;

using System.Collections.Generic;

public class Program

{

    //find single in an array of 2n+1 integer elements

    // Input : { 1, 1, 2, 2, 3, 3, 4, 4, 5}

    // Output : 5

​

    // Input : { 7, 9, 6, 8, 3, 7, 8, 6, 9}

    // Output : 3

    static void GetSingleInArray(int[] array)

    {

        Dictionary<int,int> list = new Dictionary<int,int>();

        foreach(var val in array)

        {

            if(list.ContainsKey(val))

               {

                    list[val] +=1;

               }

            else

            {

                list.Add(val,1);

            }

        }

        foreach(var val in list)

        {

            if(val.Value == 1)

            {

                Console.WriteLine(val.Key);

                break;

            }

        }

    }

    //next method with O(n) time  and O(1) space complexity

    //XOR of number with itself is 0

    //XOR of number with 0 is the number

    static void GetSingle(int[] arr)

    {

        int res= 0;

        foreach(var val in arr)

        {

            res = res^val;

            //Console.WriteLine("{0} -- {1}", val ,res);

        }

        Console.WriteLine(res);

    }

    public static void Main()

    {

        GetSingleInArray(new int[]{ 1, 1, 2, 3, 3, 3, 4, 4, 5});

        GetSingle(new int[]{ 1, 5, 2, 2, 3,4, 3, 4, 5});

    }

}