Cant use XOR as it fails when any element repeats odd number of times..... Can use hash map with O(n) time and O(n) space

only 2 possible solutions 1.) using sorting 2.) using additional space. which will be less than o(n)

Use xor

public static int NotRepeated (int ar[], int n) { int answer = -1; ArrayList arList = new ArrayList(); System.out.println(Arrays.toString(ar)); int n1 = 0; int n2 = 1; for (int i = 0; i < n; i++) { n1 = i; n2 = i +1; if (i == ar.length && (ar[i] != ar[i-1])) answer = ar[i]; else if (ar[n1] == ar[n2]) i++; else if (ar[0] != ar[1]) answer = ar[0]; else { if (ar[n1-1] == ar[n1]) { if (ar[n2] == ar[n2+1]) i++; else answer = ar[n2]; } else answer = ar[n1]; } }

sub find_odd { my @a = @{$_[0]}; my ($i, $n); $n = $a[0]; for $i (1 .. $#a) { $n = $n ^ $a[$i]; } printf("number is %s\n", $n); }

If you have an array of positive integers with only ONE non repeated integer, the easiest thing is just xor them all. Whatever you return will be the answer. Perl answer below sub findNotRepeated{ my ($arr) = @_; if(@$arr==0) { return - 1; } my $val = 0; foreach(@$arr) { $val ^= $_; } return($val); } sub findMissingElement{ my ($arr,$arr2) = @_; if(@$arr==0 || @$arr2 == 0 ) { print " arr2=" .@$arr2 . "X\n";; return - 1; } my $val = 0; foreach((@$arr , @$arr2)) { $val ^= $_; } return($val); }

This answer is in-place with O(n) complexity. A slight improvement over the space complexity of the Hash Map answer. public int returnNonRepeat(int[] input) { if(input.length < 3) return -1; else { int repeat = null; if(input[0] == input[1]) repeat = input[0]; else if(input[0] == input[2]) return input[1]; else return input[0]; for(int i = 2; i

first sort the array.n then 1)for i=1 to n { if ( element [i] !=element [i+1] ) { cout<