CareerCup

whats the Q and how is it related to median ? as anon says.

1.sort
2.get the sum of the distinct numbers sum2.
3.get the sum of all the numbers sum3.
4. the result is mod (sum3,sum2)

I am not sure, if it is optimam solution. It goes as.
Step 1 : Make an array of unique number(Say tempArray) from given array (Say OriArray)
Step 2 : Get Sum1 = 2n * sum of all numbers in tempArray
Setp 3 : Get Sum2 = sum of all numbers in OriArray
Setp 4 : get diffNum = Sum2 - Sum1
Setp 5 : DiffNum is the one which has occurances 2n+1 times in OriArray.

to find the median of the array. O(n)

@Ravi
Your solution works and seems reasonably efficient. My only qualm is how would you make an unique array of elements (step 1). You have to check all the elements in your temp array for every element of the original array. Then I guess it would be n^2.

An alternative approach if the range of the numbers is known is to use a bit vector of the size of that range. On seeing a number, we would increment that corresponding bit in the vector.
Finally we would do one more iteration to find out the extra number.

hash table, count the number.

@prolificcoder
If we know the range of numbers, ( say if the numbers are from 1-100), then we can use hash technique to prepare a tempArr of unique elements.

@prolificcoder
If we know the range of numbers, ( say if the numbers are from 1-100), then we can use hash technique to prepare a tempArr of unique elements in linear time O(n).

1) go through the array once, find out the occurrence O of array[0]
   Also while traverse, calculate the sum of the array S, multiplication of the array M.
   if O % 2 == 1
      return arra[0] (you are lucky)

2) else
      solve this equation:
      X*(2*O) + Y*(2*O+1) = S
      X^(2*O) * Y^(2*O+1) = M

      (Y is the number witch appear (2N+1) times

@Anonymous on April 15, 2009:
WTF those equations are supposed to mean ?

package com;

import java.util.HashSet;
import java.util.Set;

public class General {
static char findx(char[] arr,int length){
HashSet s=new HashSet();
for (int i = 0; i < arr.length; i++) {
if(s.add(arr[i]) == false)
s.remove(arr[i]);
}
return (Character)s.iterator().next();
}

public static void main(String[] args) {
char[] arr={'a','b','c','d','a','b','c','d','e','a'};
System.out.println(findx(arr,10));
}

}

package com;

import java.util.HashSet;
import java.util.Set;

public class General {
static char findx(char[] arr,int length){
HashSet s=new HashSet();
for (int i = 0; i < arr.length; i++) {
if(s.add(arr[i]) == false)
s.remove(arr[i]);
}
return (Character)s.iterator().next();
}

public static void main(String[] args) {
char[] arr={'a','b','c','d','a','b','c','d','e','a'};
System.out.println(findx(arr,10));
}

}