CareerCup

Time complexity = O(n)
Space = O(1)

void getEvenDuplicates()
{
	int number[]={1,6,4,1,4,5,8,8,4,6,8,8,9,7,9,5,9} ;
	int len = sizeof(number)/sizeof(number[0]);
	int tracker=0;

	for(int i=0; i< len; ++i)
	{		
		int shifted = 1<< number[i];
		tracker ^= shifted;
	}
	
	for(int i=0; i< len; ++i)
	{
		int shifted = 1<< number[i];
		if((shifted & tracker) ==  0)
		{
			tracker ^=shifted; // to avoid repeated printing of the number
			cout<<number[i]<<endl;
		}
	}
}

Hi,
If the question is three of them are odd appear times and others are even times, I can solve.
I want you can make sure, is the question correct or not?

Dictionary<int, int> counts = new Dictionary<int, int>();
            int[] input = { 1, 6, 4, 1, 4, 5, 8, 8, 4, 6, 8, 8, 9, 7, 9, 5, 9 };            
                        
            foreach( int i in input)
            {
                int count;

                if (counts.TryGetValue(i, out count))
                {
                    counts[i] = i ^ count;
                }
                else
                {
                    counts[i] = i;
                }                
            }

            foreach( var pair in counts)
            {
                if ( pair.Value == 0 )
                {
                    Console.WriteLine(pair.Key);
                }
            }

Hi, can you explain the question more detail? what is the "each integer is present an odd huber of time" meaning? Like give us some example.

Hi,
is there any specific range of numbers like 1 to n ?
and also
a XOR a XOR a ---- - -- - - odd times = a
a XOR a ---- -- -- --- - even times = 0
In our case the number that we want to find out will become zero if we perform XOR only.
I am not sure that we can find out the repeated number using XOR only.
Could you please answer am I correct or wrong?
Thanks,
srinivas

didnt know google had a bing team :) im pretty sure atleast 90% of the questions in this site are not real.

For each bit position from LSD to MSD (for value upto 9 max 4 bit poistions)
Go through the array and move all the values with bit 0 to the left and 1 to the right
have two pointer one from left and right
increment the left pointer until an interger with bit 1 in digit i is encountered
decrement the right pointer until an interger with bit 0 in digit i is encountered
swap these two
proceed above until left < right
This would have split the numbers into two groups
Performing this for all the 4 bits would have grouped the same numbers next to each other
now scan through the array from 0 to n-1
xor i+1..n until the number is different - count the occurence
print if count is even
now the new number to xor was the different one encountered during xor

Total number of scans through the array = no_bits * n + 1 * n = (no_bits+1) * n = O(N)
As the sort / grouping was done inplace no additional space used.
NOTE:Stack space might be used if the split on groups is performed recursively, just the left and right pointers for each recursive call

public class Fun {

    // configured for positive, single digit integers per sample input.
    static final int DIGITS = 1;

    public static void main(String[] args) {

        int[] counters = new int[10 * DIGITS];
        int[] data = { 1, 6, 4, 1, 4, 5, 8, 8, 4, 6, 8, 8, 9, 7, 9, 5, 9 };

        for (int x = 0; x < data.length; x++) {
            int index = data[x];

            if (index > counters.length || index < 0) {
                throw new RuntimeException("input Integer " + index + " out of range for data structure");
            }

            if (counters[index] == 0) {
                counters[index] = 1;
            }
            else {
                counters[index] ^= -1; // XOR with negative 1 to create one's
                                       // complement per question requirement
                // counters[index] = ~counters[index]; // equivalently, use
                // uniary complement operator to create one's complement
            }

        }

        // show the counter results
        // 0 means not encountered
        // +1 means odd
        // -2 means even (one's complement of 1 = -2 and vice versa)
        //System.out.println(Arrays.toString(counters));

        // show the even numbers
        for (int x = 0; x < counters.length; x++) {
            if (counters[x] == -2) {
                System.out.println(x);
            }
        }
    }
}

import Foundation

class Play {
    
    func play() {
        
        let numbers: Int[] = [1,6,4,1,4,5,8,8,4,6,8,8,9,7,9,5,9]
        
        var dataBank: Int = 0
        
        for number in numbers {
            var slot = 1 << number
            dataBank ^= slot // Toggle the bit everytime we find the same number in the sequence
        }
        
        dataBank = ~dataBank // Invert it so now the posistive bits represent the EVEN numbers we are looking for
        
        for number in numbers {
            if dataBank & (1 << number) > 0
            {
                // TODO: The even numbers will appear at multiple times
                println("Even number found: \(number)")
            }
        }
    }

unsigned int input[] = {1,6,4,1,4,5,8,8,4,6,8,8,9,7,9,5,9};
	unsigned int oddInputs=0;
	for( unsigned int i = 0 ; i < sizeof(input)/sizeof(input[0]) ; ++i){
		oddInputs ^= ( 1 << input[i]);
	}
	
	std::cout << "OddInteger { ";

	for( unsigned int i = 0 ; i < sizeof(input)/sizeof(input[0]) ; ++i){
		if(( oddInputs & ( 1 << input[i])) == 0 ){
			oddInputs |= ( 1 << input[i] );
			std::cout <<  input[i] << " ";
		}
	}
	std::cout << "}";

I think we're misunderstanding this a bit. O(1) means constant space - that means the space is not varying with the input n. So in that case we can very well assume an extra int arr[10] and then index the values of the original input straight into arr[value]++ ?

I think the sample output in the question is incorrect. It should be 1, 6, 8 and 5. From the input, it seems that 5 is repeated twice, which means it should be in the output.

Am I missing something or does the question specify we can arbitrarily pick 3?

this is for sure needs more questions to ask before attempting to solve,

1. what is the domain size, according to example [0-10] ( we will assume ),
so you just need a constant array, size 10, in this case and pass through the data
increment per index in second array and second pass print even or odd numbers

so memory O(1) - constant, time: N + 10, O(N)

Try to use a Bit version Trie?
Use a bit (namely, "time") to determine if a node represents a number, so you can use XOR ( time^=1 ) to determine if it appears odd times (if time == 1).
Traverse the trie, print those nodes with time == 1 (You also need to reconstruct the value of the node).

The time complexity is O(32*N) for 4-byte Integers = O(N), and the space complexity is bound by the maximum number of nodes in the trie (2^32). Although it seems large, it's O(1) by definition.

1) Create a HashMap
2) Iterate over the array
3) If HashMap contains the entry the take put the value^1
4) Else put 1 for that entry
5) In the end numbers which are present even number of times will have value 0 in hash map

Code:

public static void findEvenOccurringNumbers(int[] a)
	{
		Map<Integer, Integer> hash = new HashMap<Integer, Integer>();

		for (int num : a)
		{
			if (hash.containsKey(num))
			{
				hash.put(num, hash.get(num) ^ 1);
			}
			else
			{
				hash.put(num, 1);
			}
		}

		for (Entry<Integer, Integer> entry : hash.entrySet())
		{
			if (entry.getValue() == 0)
			{
				System.out.println(entry.getKey());
			}
		}
	}

First sort the Array

public void FindEvenOccurance(int[] arr,int size)
{
int count,j;
for(int i=0;i<size;i++)
{
count = 1;
j=i+1;
while(j<size && arr[j]==arr[i])
{
count++;
j++;
}
if(count %2==0)
Console.WriteLine("Number"+ arr[i]);
i = j - 1;
}
}

public static void main(String[] args)
    {
        Integer [] input  = {1,6,4,1,4,5,8,8,4,6,8,8,9,7,9,5,9};

        findEvenOccur(input);
    }

    public static void findEvenOccur(Integer [] input){

        if(input == null || input.length == 0)
            return;

        HashMap<Integer, Boolean> countingMap = new HashMap<Integer, Boolean>();

        for(Integer i : input)
        {
            Boolean isOdd = countingMap.get(i);
            if(isOdd == null)
                isOdd = false;
            countingMap.put(i, isOdd ^ true);  //even occurence will have false, odd will have true.
        }

        for(Integer i : countingMap.keySet())
        {
            if(!countingMap.get(i))
                System.out.println(i);
        }
    }

O(n) time
O(k) for the hashmap where k = the range of the numbers, and it's k <= n -3. Assume large n and small k, then it's constant.

import java.util.*;
public class SortNumber{

public static void main(String []args){

Integer[] hari= {1,6,4,1,4,5,8,8,4,6,8,8,9,7,9,5,9};

ArrayList<Integer> newIn = new ArrayList<Integer>(Arrays.asList(hari));

Set<Integer> finalList = new HashSet<Integer>();

for(Integer a: newIn){
int r = Collections.frequency(newIn, a);

if(r%2 == 0){
finalList.add(a);
}
}

System.out.println(finalList);
}
}

import java.util.*;
public class SortNumber{

public static void main(String []args){

Integer[] hari= {1,6,4,1,4,5,8,8,4,6,8,8,9,7,9,5,9};

ArrayList<Integer> newIn = new ArrayList<Integer>(Arrays.asList(hari));

Set<Integer> finalList = new HashSet<Integer>();

for(Integer a: newIn){
int r = Collections.frequency(newIn, a);

if(r%2 == 0){
finalList.add(a);
}
}

System.out.println(finalList);
}
}

Time COmplexity =O(n)
Space= O(1)

void getEvenDuplicates()
{
	int number[]={1,6,4,1,4,5,8,8,4,6,8,8,9,7,9,5,9} ;
	int len = sizeof(number)/sizeof(number[0]);
	int tracker=0;

	for(int i=0; i< len; ++i)
	{		
		int shifted = 1<< number[i];
		tracker ^= shifted;
	}
	
	for(int i=0; i< len; ++i)
	{
		int shifted = 1<< number[i];
		if((shifted & tracker) ==  0)
		{
			tracker ^=shifted; // to avoid repeated printing of the number
			cout<<number[i]<<endl;
		}
	}
}

in ur example I/O 5 has even frequency

For this question, I think we can do it in O(n) time.
1. XOR all the numbers, then we will know which bit appears odd times.
2. As we get the result of step 1, we XOR all the numbers which contains 1 at kth bit. Then we can get three numbers after three loops. That's the answer we want.

The algorithm looks like this:

List<Integer> result = new ArrayList<Integer>();

int temp = num[0];
for (int i = 1; i < num.length; i++) ｛
temp ^= num[i];
｝

for (int i = 0; i < 32; i++) {
int t = 0;
if ((1 << i) & temp == (1 << i)) {
for (int j = 0; j < num.length; j++) {
if ((1 << i) & num[j] == (1 << j)) {
t ^= nump[j];
}
}
result.add(t);
if (result.size() == 3) {
break;
}
}
}

return result;

For this question, I think we can do it in O(n) time.
1. XOR all the numbers, then we will know which bit appears odd times.
2. As we get the result of step 1, we XOR all the numbers which contains 1 at kth bit. Then we can get three numbers after three loops. That's the answer we want.

The algorithm looks like this:

List<Integer> result = new ArrayList<Integer>();

int temp = num[0];
for (int i = 1; i < num.length; i++) ｛
temp ^= num[i];
｝

for (int i = 0; i < 32; i++) {
int t = 0;
for (int j = 0; j < num.length; j++) {
if ((1 << i) & num[j] == (1 << j)) {
t ^= nump[j];
}
}
result.add(t);
if (result.size() == 3) {
break;
}
}

return result;

public static void numTimes(int arr[]) {

HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
int count = 1;
int tempVar;
// Sort array
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1; j++) {
if (arr[i] < arr[j + 1]) {
tempVar = arr[j + 1];
arr[j + 1] = arr[i];
arr[i] = tempVar;
}
}
}

// add values in hash map
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] == arr[i + 1]) {
count++;
} else {
hm.put(arr[i], count);
count = 1;
}

}

for (Map.Entry<Integer, Integer> e : hm.entrySet()) {
if (e.getValue() % 2 == 0) {
System.out.print(e.getKey() + " ");
}
}

}

run quick sort with O(nlogn) average case, then check if even or odd

public void getEven(int array[], int max){
		Sort(array, 0, max);
		int checker = 1;
		int val = array[0];
		for(int i = 1; i<=max; i++){
			if(array[i] == val){
				checker = checker ^1;
			}
			else{
				if(checker == 0)
					System.out.println( array[i-1]);
				val = array[i];
				checker = 1;
			}
		}
		if(checker == 0)
			System.out.println( array[max]);
	}
	
	private void QuickSort(int array[], int left, int right){
		  int i = left, j = right;
		  int tmp;
		  int pivot = (right-left)/2 + left;
		  while (i <= j) {
		        while (array[i] < array[pivot])
		              i++;
		        while (array[j] > array[pivot])
		              j--;
		        if (i <= j) {
		              tmp = array[i];
		              array[i] = array[j];
		              array[j] = tmp;
		              i++;
		              j--;
		    }
		}
		if (left < j)
			Sort(array, left, j);
		if (i < right)
			Sort(array, i, right);
	}

run QuickSort O(nlogn) then check for even/odd

public void getEven(int array[], int max){
		Sort(array, 0, max);
		int checker = 1;
		int val = array[0];
		for(int i = 1; i<=max; i++){
			if(array[i] == val){
				checker = checker ^1;
			}
			else{
				if(checker == 0)
					System.out.println( array[i-1]);
				val = array[i];
				checker = 1;
			}
		}
		if(checker == 0)
			System.out.println( array[max]);
	}
	
	private void QuickSort(int array[], int left, int right){
		  int i = left, j = right;
		  int tmp;
		  int pivot = (right-left)/2 + left;
		  while (i <= j) {
		        while (array[i] < array[pivot])
		              i++;
		        while (array[j] > array[pivot])
		              j--;
		        if (i <= j) {
		              tmp = array[i];
		              array[i] = array[j];
		              array[j] = tmp;
		              i++;
		              j--;
		    }
		}
		if (left < j)
			Sort(array, left, j);
		if (i < right)
			Sort(array, i, right);

}

assume x1,..,xn: odd times,
y1,..,ym: even

x1^x2^...^xn ^ y1 ^...^ym = x1^x2^...^xm = t.
--> t ^ x[i] < t.
and t ^ y[j] > t.

complex: O(N)
space: O(1)

int p[] = {1,6,4,1,4,5,8,8,4,6,8,8,9,7,9,5,9};

int cnt = 1;
int n = 17;
int pos;
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
if (p[i] == p[j])
{
cnt++;
pos = j;
for (; pos < n - 1; pos++)
p[pos] = p[pos + 1];
j--;
n--;
}
}
if (cnt % 2 == 0)
cout << p[i] << endl;
cnt = 1;
}

Im not sure if this would be the solution.
I would create empty array, and start adding the items of the array. each new addition would do a XOR comparation with the items of the new array. in case XOR result is 0, it means we have, at that moment, a pair, so we can proceed to delete the item from the array. at the end of the full array we would end with the result array.

not really sure that the time complexity is o(N) exactly, but should be pretty close.

Bing team at Google!!! LOL

The way I would approach this problem is that I would create a bitmask ( assuming that the digits that are being used are 0-9). As I go over the array I would take the bitmask -lets call it x - and take x XOR (1 << num) . When I am done iterating over the array I would go over the bitmask and see which bits have 0.

Sort the array, then compare the items, if they are equal using xOR, leave them in there and try with i+1 (compare xor with 3 elements) if they are odd, then try it with the 4th element. this way we know how many comparations of the numbers we are having and when they are not the same number (xOR is not 0). this way we know which numbers are odd and we can remove them from the array. The comparation index will jump to the last compared item. time complexity o(N) space o(1)

5 appears an even number of times but is not included in the output. Typo?

XOR based only? Stop posting "puzzles". Google would never impose idiotic restrictions like these.

It is unlikely Google asked this. And if someone did, the committee SHOULD throw it out (Unless they were busy that day).

Dictionary<int, int> counts = new Dictionary<int, int>();
            int[] input = { 1, 6, 4, 1, 4, 5, 8, 8, 4, 6, 8, 8, 9, 7, 9, 5, 9 };            
                        
            foreach( int i in input)
            {
                int count;

                if (counts.TryGetValue(i, out count))
                {
                    counts[i] = i ^ count;
                }
                else
                {
                    counts[i] = i;
                }                
            }

            foreach( var pair in counts)
            {
                if ( pair.Value == 0 )
                {
                    Console.WriteLine(pair.Key);
                }
            }

The space complexity of O(1) is little bit on the harsher side but here are the steps to get required output

Step1: Sort the integer array using LSD Redix sort. LSD Redix sort uses O(k.N) time where k is a constant and depends on the length of the value to be sorted. For example for integer it will be 32 bit. It does not depend on the length of the input.

For LSD redix sort, ideally a new array is used to store the indexes of the input elements. But instead due to O(1) space requirement, we can use a a String variable which will store indexes.
So for input 1 appearing 3 times, 4 appearing 2 time and 15 appearing 3 times, the string can be
countString = "1-3_4-2_15-3_... etc
indexString would then be appropriately created identifying the indices for the elements.

Step2: After sorting the array, the array will have some elements 3 times and some 2 times.

Now start from index 0, i=0
If (i ^ i+1 ^ i+2) == i then ignore this number and move i = i+3;
if (i ^ i+1 ^ i+2) != i then print this number and move i = i+2;

Total time taken:
Step1: For LSD redix sort O(k.N) --> k is constant. Space complexity with string hack = O(1)

Step2: For loop O(N)

- Open a 2^32 sized bit array (512 mb) and initialize it to all 0.
- Scan the given array, for every integer, "toggle" the corresponding bit:
e.g. for integer 12, if 12th bit is 0, set it to 1, if it was 1 (saw 12 before) set it to 0
-- now, you will have bits set to 1 for odd elements, and bits set to 0 for even elements
- Scan the given array once more, check the bit for every element, if you see a bit 0 for any element, emit that

Inspired by Phoenix's solution I found another solution that doesn't need to alter the input array. I put all the code here: 1. My solution; 2 Solution based on Phoenix's 3 test cases:

#include <time.h>
#include <stdlib.h>
#include <assert.h>
#include <algorithm>
#include <iostream>
#include <utility>

#include <vector>

int firstBit1( int x ){
	//given x, return the index of the first 1 bit of x
	for( int i = 0; x ; x >>= 1, ++i ){
		if( x&1 )//test whether the i-th bit of x is 1
			return i;
	}
	return -1;
}

			
bool find2( std::vector<int> &arr, int &a, int &b, int skip ){
	//given a, b occur odd times in arr, others occur even times, return a, b
	//with the extra condition: skip all elements that equal to "skip"
	int x = 0;
	for( int v : arr ){
		if( v==skip )continue;
		x ^= v;
	}
	int bit = firstBit1( x );
	if( bit == -1 )return false;//invalid input

	a = b = 0;
	int mask = (1<<bit);
	for( int v : arr ){
		if( v==skip )continue;
		if( v&mask )a ^= v;
		else  b^= v;
	}
	return true;
}

bool found( std::vector<int> &arr, int a ){
	//check whether "a" occurs odd times in arr
	bool odd = false;
	for( int v : arr )if( v==a )odd = !odd;
	return odd;
}

bool find3( std::vector<int> &arr, int &a, int &b, int &c ){
	a = b = 0;
	int bits = sizeof(int)*8;
	for( int i = 0;i < bits; ++ i ){
		int mask = (1<<i);
		for( int v : arr ){
			if( v&mask )a ^= v;
			else b^= v;
		}
		if( found(arr, a) ){
			return find2( arr, b, c, a );
		}
		else if( found(arr, b) ){
			return find2( arr, a, c, b );
		}
	}
	return false;
}

void createTestCase( std::vector<int> &arr, int &a, int &b, int &c ){
	//3 different numbers a, b, c
	int max = 10, max_occur = 10;
	b = rand()%max;
	if( b == 0 || b==max-1 )b = max/2;
	a = rand()%b;
	c = b + 1 + rand()%(max-1-b);
	std::vector<int> different_numbers(max, 0);

	different_numbers[a] = (2*(rand()%max_occur)+1)%max_occur;
	different_numbers[b] = (2*(rand()%max_occur)+1)%max_occur;
	different_numbers[c] = (2*(rand()%max_occur)+1)%max_occur;

	int n = 0;	
	for( int i = 0;i < max; ++ i ){
		if( different_numbers[i] == 0 ){
			different_numbers[i] = (2*(rand()%max_occur))%max_occur;
		}
		n += different_numbers[i];
	}

	arr.resize(n);
	for( int i = 0, k = 0; i < max; ++ i ){
		for( int j = 0;j < different_numbers[i]; ++ j ){
			arr[k++] = i;
		}
	}

	std::random_shuffle( arr.begin(), arr.end() );
}

void bitBasedGroup( std::vector<int>::iterator from, std::vector<int>::iterator to, int bit, int max_bits ){
	if( bit == max_bits || to <= from )return;

	auto bit0_it = from - 1;
	int mask = (1<<bit);
	for( auto it = from; it != to; it ++ ){
		if( 0 == (mask & *it) ){
			std::swap( *it, *(++bit0_it) );
		}
	}
//	for( auto it = from; it != to; it ++ )std::cout << *it << ' ';
//	std::cout << std::endl;
	
	++ bit0_it;
	bitBasedGroup( from, bit0_it, bit+1, max_bits );
	bitBasedGroup( bit0_it, to, bit+1, max_bits );	
}

void printArray( std::vector<int> &arr ){
	std::cout << '[';
	for( int v : arr ) std::cout << v << ' ';
	std::cout << ']' << std::endl;
}

void bitBasedGroup( std::vector<int> &arr ){
	int max = *std::max_element( arr.begin(), arr.end() );
	int bits = 0;
	for( ; max; max >>=1 ) ++ bits;
	bitBasedGroup( arr.begin(), arr.end(), 0, bits );
}

bool find3ByGroup( std::vector<int> &arr, int &a, int &b, int &c ){
	if( arr.size() < 3 )return false;

	bitBasedGroup( arr );
	
	int X[3], found = 0;
	int prev = arr[0];
	bool odd = true;
	for( int i = 1;i < arr.size(); ++ i ){
		int v = arr[i];
		if( v == prev ){
			odd = !odd;
		}
		else{
			if( odd && found<3 )X[found++] = prev;
			prev = v; odd = true;
		}
	}
	if( odd && found<3 )X[found++] = prev;
	if( found != 3 )return false;
	a = X[0]; b = X[1]; c = X[2];
	return true;
}

int main(){
	srand( time(0) );

	for( int i = 0;i < 1000; ++ i ){
		int X[3];
		std::vector<int> arr;
		createTestCase( arr, X[0], X[1], X[2] );
		printArray( arr );
		std::cout << "a:" << X[0] << ' ' << "b:" << X[1] << ' ' << "c:" << X[2] << std::endl;

		int Y[3];
		find3( arr, Y[0], Y[1], Y[2] );
		std::sort( Y, Y+3 );
		assert( std::equal(X,X+3,Y) );

		find3ByGroup( arr, Y[0], Y[1], Y[2] );		
		printArray( arr );
		std::sort( Y, Y+3 );
		assert( std::equal(X,X+3,Y) );
	}	
}

start with the first element of the array
xor it with the entire array and count the number of zeros.
if it is even, display it and delete its occurrences from the array.
repeat until array is empty or end of array is reached
deleting = O(n)

1) Create a HashMap
2) Iterate over the array
3) If HashMap contains the entry the take put the value^1
4) Else put 1 for that entry
5) In the end numbers which are present even number of times will have value 0 in hash map

Code:

public static void findEvenOccurringNumbers(int[] a)
	{
		Map<Integer, Integer> hash = new HashMap<Integer, Integer>();

		for (int num : a)
		{
			if (hash.containsKey(num))
			{
				hash.put(num, hash.get(num) ^ 1);
			}
			else
			{
				hash.put(num, 1);
			}
		}

		for (Entry<Integer, Integer> entry : hash.entrySet())
		{
			if (entry.getValue() == 0)
			{
				System.out.println(entry.getKey());
			}
		}
	}

May be this would be better:

public static final int[] findDuplicates(final int[] data) {
    // take a copy of the data.
    int[] sorted = Arrays.copyOf(data, data.length);
    // sort it. This is O(n log(n)) which will be the bulk of our time.
    Arrays.sort(sorted);

    // now scan the sorted data for even-numbered sequences of values.
    int len = 0;
    boolean even = false;
    // sorted[0] is our first sequence, and currently it is not even.
    // note that the scan starts at position 1.
    for (int i = 1; i < sorted.length; i++) {
        if (sorted[i] == sorted[len]) {
            // this element is the same as the sequence, so 'count' the even-ness.
            even = !even;
        } else {
            // this element is different to our sequence, it's a new sequence.
            if (even) {
                // the old sequence had an even count, so we 'preserve' it.
                len++;
            }
            // move the value of the new sequence to the 'beginning'.
            sorted[len] = sorted[i];
            // and the new sequence is odd.
            even = false;
        }
    }
    if (even) {
        // the last sequence was even, we preserve it.
        len++;
    }
    // return the first part of the array, which contains the even sequence values.
    return Arrays.copyOf(sorted, len);

}

Hashtable table=new Hashtable();
for(int i=0;i<n;i++)
{
if(table.contains(arr[i])
{
table.remove(arr[i]);
}
else
{
table.add(arr[i]);
}
}

// table now contains only odd numbered value.

foreach(int no in table.keys)
{
// print no;
}