i did it in c++ by using a map. when iterating through the list, it checks if the number is a key in the map, if it is not, then map[num] = 1, if it does exist, map[num]++. finally iterate through the map and return when a value is 1
An easy (in place) n ln (n) solution is obtained by sorting the array, comparing each 2 elements consecutive elements (n/2 comparisons) and returning the first elements where you get non equality. Lonely elements will be at odd index in a sorted array.
This is what I came up with in Python 3: ``` # will return only the *first* integer that appears only once def lonelyinteger(a): length = len(a) list_before_iteration = list(a) for i in range(0,length): list_after_iteration = list(a) value_of_current_index = list_after_iteration.pop(i) if list_after_iteration.__contains__(value_of_current_index): continue else: return value_of_current_index ``` Basically my idea was: - go one index at a time - record the value of the index and also remove it temporarily from the list - check if the mutated list still contains another copy of that value; If it does, move on to next index, else return that value
oh and for those who are not familiar with python 3, the built-in `pop` is the real hero here. the pop function both return the value at the given index, and also mutates the list at the same time. therefore, when we check the list from before the for loop and compare it to the local list in the for loop that has removed that index, we can simply check if another copy of the index's value still remains in the mutated list.
Nice video thanks, but the bitwise XOR operator will only work if the repeated values are in pairs so the XOR gets 0, for this array [1,4,1,1,1,1,3,3,3] it won't work ;)
Bitwise operators are a bit weird. You could do it like this in a single iteration. Time complexity should be O(n) while space complexity is a bit worse than your solution, but I don't feel like space complexity is a concern nowadays. public static int lonelyinteger(List a) { Set firstSet = new HashSet(); // Contains all elements Set secondSet = new HashSet(); // Contains duplicated elements only for (int i : a) { if (!firstSet.contains(i)) { firstSet.add(i); } else { secondSet.add(i); } } firstSet.removeAll(secondSet); return firstSet.stream().findFirst().orElse(-1); }
