CareerCup

First method:

You use an array of size 256-initialized to 0(considering ascii), in pass one increment corresponding element for each occurance in input string.

In second pass see whether the element occurs exactly once, in that case return the element. complexity - 2n - 0(n)

2nd way:

Make a copy of the input string, sort this copied version.
make a pass through input string, for each character determine in logn times whether it occurs once or more times.

Complexity 0(nlogn)

Is there any better soln???

Non-duplicate implies it appears an odd # of times(1). Assume a duplicate is at most 2. XOR from left to right to get a result K. Then XOR K to find the missing duplicate. This is O(n) running time and O(1) space. (a^b)^a = a ^(b^a) because XOR is a 1-1 function.

both of jason's way work although they both require o(n) space.

Jack's way doesn't solve this problem because you can't assume that there is only one non-duplicate nor that any duplicates only have two instances.

o(n^2) time and o(1) space algorithm also exists.
o(n) time and o(n) space algorithm exists (Jason's).

Are there any better algorithms?

Jason's method 1 gives O(1) space.. It always takes a[256] and doesnt change depending on the size of the string..

Use a Hash table...
Has string twice to check which is non duplicate