CareerCup

The idea is to for every bit position count the number of 1's mod 3. The resulting number will be the answer.It is possible to do it in O(n) using bitwise operations. Will provide code soon.

O(n) solution using O(1) space

def unique(lst):
    # For every bit we need to store a 2-bit counter
    # 00 01 10 are its possible values.
    # Lower bit of each counter
    counter_lower = 0
    # Higher bit of each counter
    counter_higher = 0
    for number in lst:
        # f(high_bit, low_bit, number_bit) = new_high_bit, new_low_bit
        # Just note that we don't have to do anything if number_bit isn't set
        new_counter_lower = counter_lower
        new_counter_higher = counter_higher

        # f(00, 1) = 01
        # Bits which are set and both counters bits are zero
        both_zero = number & (~counter_lower & ~counter_higher)
        new_counter_lower |= both_zero

        # f(01, 1) = 10
        # Bits for which only lower counter is set
        lower_set = number & counter_lower
        # unset lower bit
        new_counter_lower &= (~lower_set)
        # set higher bit
        new_counter_higher |= lower_set

        # f(10, 1) = 00
        # Bits for which only higher counter is set
        higher_set = number & counter_higher
        # Drop high counter to 0
        new_counter_higher &= (~higher_set)

        counter_lower = new_counter_lower
        counter_higher = new_counter_higher
        # just a sanity check that each counter is ok
        assert counter_lower & counter_higher == 0
    # since we've taken number of bits mod 3, the lower counter will have our unique number.
    assert counter_higher == 0, "incorrect input"
    return new_counter_lower

assert unique([3,19,2,2,2,2,2,2,3,3]) == 19
assert unique([3,19,19,19,8,2,2,2,2,2,2,3,3]) == 8

In O(N) with python

def find_num(L):
	counts = {}
	for l in L:
		if counts.get(l):
			counts[l] += 1
		else:
			counts[l] = 1
	
	for el in counts:
		if counts[el] == 1:
			return el

private int findOneValue(int[] arr){
		
		int maxValue = Integer.MIN_VALUE;
		for( int value : arr ){
			maxValue = Math.max(value, maxValue);
		}
		
		BitSet set1 = new BitSet(maxValue+1);
		BitSet set2 = new BitSet(maxValue+1);
		
		for( int value : arr ){
			if( ! set1.get(value) ){
				set1.set(value);
			}
			else {
				set2.set(value);
			}
		}
		
		set1.xor(set2);
		
		return set1.length()-1;
	}

Count every bit of the element in this array, after Count, then mode 3, so the left bit should be the element which appear once.

int GetSingleNumber(vector<int>& irvector)
{
	vector<int> lvBitCount;
	for(int i = 0; i< irvector.size(); i++)
	{
		int Cur = irvector[i];
		int BitC = 0;
		while(Cur)
		{
			if(Cur & 1)
			{
				while(BitC >= lvBitCount.size())
				{
					lvBitCount.push_back(0);
				}
				lvBitCount[BitC] += 1;
			}
			Cur = Cur >> 1;
			BitC ++;
		}
	}

	reverse(lvBitCount.begin(), lvBitCount.end());
	int result = 0;
	for(int i = 0; i< lvBitCount.size(); i++)
	{
		lvBitCount[i] = lvBitCount[i] % 3;
		result = (result << 1) + lvBitCount[i];
	}
	return result;
}

we can do this in O(n).. by frequency measuring... just note the frequencies of all the elemnts.. this can be done in O(n) time and then check the whole array if the frequency is 1 or not.. O(n) time.. thus checked!

for(i=0;i<n;i++)
{
arrfreq[arrnumbrs[i]]++;
}
for(i=0;i<rangeofnumbers;i++)
{
if(arrfreq[i]==1)
printf("i");
break;
}

public static void main(String[] args) {
		int[] a=new int[]{2,3,3,3};
		int number=0;
		int powerOfTwo=1;
		boolean flag=true;
		while(flag){
			flag=false;
			int countLower=0;
			for(int i=0;i<a.length;i++){
				if((a[i]&1)==1){
					countLower++;
				}
				a[i]=a[i]>>1;
				if(a[i]!=0)
					flag=true;
			}
			number+=(countLower%3)*powerOfTwo;
			powerOfTwo*=2;
			
		}
		System.out.println(number);

}

This is a really great answer.

One could argue it is in fact O(n Log(n)) as there will be log(n) bits but it is close enough to O(1) as far as I am concerned.

The interesting thing is to think about this solution why it worked and be ready to apply the same brilliant thinking to other problems. I wonder if there is a name for this kind of thing.

I believe this is linear time O(n), as lookup, insert, delete using hashmaps without collisions should be O(1). Works to find any unique values, it's not necessary that all multiple examples are in threes. It's assumed there is only one number which only appears once, but it's trivial to show multiple examples using a loop through "candidates" at the end.

int main()
{
    std::unordered_set<int> candidates;
    std::unordered_map<int,int> previously_seen;
    const int TEST_SIZE = 10;
    int test_data[TEST_SIZE] = { 2,3,5,1,2,2,5,3,5,3 };
    std::unordered_map<int, int>::iterator iter;

    for( int idx = 0; idx < TEST_SIZE; ++idx )
    {
        iter = previously_seen.find( test_data[idx] );
        if( iter != previously_seen.end() )
        {
            if( ++(iter->second) == 2 )
            {
                // if this is the second occurrence,
                // erase from candidates
                candidates.erase( iter->first );
            }
        }
        else
        {
            previously_seen.insert( std::make_pair(test_data[idx], 1) );
            candidates.insert( test_data[idx] );
        }
    }
    if( candidates.size() == 1 )
    {
        std::cout << "Answer is: " << *candidates.begin() << std::endl;
    }

    return 0;
}

C# O(n), using linq.single as a shortcut at the end.

using System.IO;
using System;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
       int[] inputs = { 2,3,5,1,2,2,5,3,5,3,6,6,103,6,7,7,7,1,1,18,18,18 };
       IDictionary<int, int> hash = new Dictionary<int,int>();
       
       foreach(var i in inputs)
       {
           if (!hash.ContainsKey(i))
           {
                hash.Add(i, 0);
           }
           hash[i]++;
       }
       
       var singleOccur = hash.Single(h => h.Value == 1).Key;
       Console.WriteLine(singleOccur);
    }
}

Hey guys, check it out. The idea is to make a bitwise sum of all the numbers modulo 3 (I mean, every i-th bit of the result is a sum modulo 3 of i-th bit across all the numbers). Since we have no such an operation, let's emulate it using bitwise operations. Let us have 2 words, representing our sum modulo 3 (one word is for lower bit of the sums, and one word for higher bit). All we need to do is to implement an operation (x + y) mod 3, where x is a 2-bit number, and y is a 1-bit number. And we want to do it in O(1) using bitwise operaions. If you know how computer adders/counters work, it is pretty much it (check Half_adder and Counter on wikipedia).

Here is the code of a function:

template<typename T>
T getUniqueNumber(const T *begin, const T *end) {
    T low = 0, high = 0;
    for (; begin + 1 <= end; ++begin) {
        high ^= low & *begin;
        low ^= *begin;
        const T overflow = high & low;
        low ^= overflow;
        high ^= overflow;
    }
    return low;
}

Objective C solution to this problem,
    NSArray *threeTimesArray = @[@2,@3,@5,@1,@2,@2,@5,@3,@5,@3];
    __block NSNumber *uniqueNumer ;
    [threeTimesArray enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
        NSMutableArray *remainingArray = [[NSMutableArray alloc]initWithArray:threeTimesArray];
        [remainingArray removeObjectAtIndex:idx];
        if (![remainingArray containsObject:obj]) {
            uniqueNumer = obj;
        }
    }];

public static int findUniqueNum(int A[], int times){
		int N = A.length;
		
		Arrays.sort(A);
		for (int j = 0 ; j < N ; j++)
		System.out.print(A[j] + " ");
		System.out.println();
		int i = 0 ;
		for ( ; i < N-1 ; i+=times ){
			if (A[i] == A[i+1]){
				continue;
			}
			else {
				break;
			}
		}
		return A[i];
	}

package test;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;


public class Hashtest {
	public static void main(String [] args)
	{
		String str = null;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			str=br.readLine();
		} catch (IOException e) {
			e.printStackTrace();
		}
		String [] tokens;
		tokens=str.split(" ");
		Map<String, Integer> hmap = new HashMap<String, Integer>();
		for (String string : tokens) {
			if(hmap.containsKey(string))
			{
				int i=hmap.get(string).intValue();
				hmap.put(string, i+1);
			}
			else
			{
				hmap.put(string, 1);
			}
		}
		for(Entry<String, Integer> e:hmap.entrySet())
		{
			if(e.getValue().equals(1))
			{
				System.out.println(e.getKey());
			}
		}
		
	}
}

Count Sort is best :)
complexity : O(cn) ... c is some constant time ..

sum all of them and do mod 3
time complexity -> O(n)
space complexity -> O(1)

if the input numbers are positive integers then the following is a solution in O(n). if negative is involved there can be a bit of search involved at the end.

unsigned return_unique_num(const std::vector<unsigned>& input)
{
    std::unordered_set<unsigned> unique_input;
    for (auto i : input)
      unique_input.insert(i);
    long long input_mult = 1;
    long long unique_input_mult = 1;
    std::for_each(input.begin(), input.end(), [&](unsigned i) {input_mult *= i; });
    std::for_each(unique_input.begin(), unique_input.end(), [&](unsigned i) {unique_input_mult *= i; });

    long long cube_unique_input_mult = unique_input_mult * unique_input_mult * unique_input_mult;

    return static_cast<unsigned>(sqrt(cube_unique_input_mult / input_mult));
}

Version with handling zero's and negative numbers as well as positives.

#include <vector>
#include <unordered_set>
#include <algorithm>
#include <cmath>

unsigned return_unique_num(const std::vector<int>& input)
{
  int zeros = std::count(input.begin(), input.end(), 0);
  if (zeros == 1)
    return 0;

    std::unordered_set<int> unique_input;
    for (auto i : input)
      unique_input.insert(i);
    long long input_mult = 1;
    long long unique_input_mult = 1;
    std::for_each(input.begin(), input.end(), [&](int i) {if(i) input_mult *= i; });
    std::for_each(unique_input.begin(), unique_input.end(), [&](int i) {if(i) unique_input_mult *= i; });

    long long cube_unique_input_mult = unique_input_mult * unique_input_mult * unique_input_mult;



    int ret = static_cast<int>(sqrt(cube_unique_input_mult / input_mult));
    if (std::count(input.begin(), input.end(), ret) == 1)
      return ret;
    return -ret;
}

using System;
using System.Collections.Generic;
class SingularityFinder
{
    static void Main()
    {
        int[] arr = {2,3,5,1,2,2,5,3,5,3 };
        List<int> entries = new List<int>();
        bool bl = false;
        for (int i = 0; i < arr.Length - 1; i++)
        {
            bl = false;
            if (!entries.Contains(arr[i]))
            {
                entries.Add(arr[i]);
                for (int j = i + 1; j < arr.Length; j++)
                {
                    if (arr[i] == arr[j])
                    {
                        bl = true;
                        break;
                    }
                }
                if (!bl)
                {
                    Console.WriteLine(arr[i]);
                    bl = true;
                    break;
                }
            }
        }
        if (!bl)
        {
            Console.WriteLine(arr[arr.Length - 1]);
        }
    }

}