Blogs Hub

Find a single occurring element in an array where each element occurred twice. - MiniTV

Find a single occurring element in an array where each element occurred twice. - मिनी टीवी

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

 

Note:

 

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

 

Example 1:

 

Input: [2,2,1]

Output: 1

 

Example 2:

 

Input: [4,1,2,1,2]

Output: 4

 

Solution:

using System;
using System.Collections.Generic;
using System.Text;

namespace LeetCode.Easy
{
    class SingleNumberSolution
    {
        public void execute()
        {

            var input = new int[] { 2, 2, 1 };
            int res = SingleNumber(input);
        }

        public int SingleNumber(int[] nums)
        {
            int val = nums[0];
            for (int i = 1; i < nums.Length; i++)
            {
                val = val ^ nums[i];
            }            
            return val;
        }
    }
}

 

Time Complexity: O(n)

Space Complexity: O(1)