Community

Start a Thread


Notifications
Subscribe You’re not receiving notifications from this thread.

Lonely Number (Main Thread)

Here is the interview question prompt, presented for reference.

In a given array of numbers, one element will show up once and the others will each show up twice. Can you find the number that only appears once in O(n) linear time? Bonus points if you can do it in O(1) space as well.

lonelyNumber([4, 4, 6, 1, 3, 1, 3])
// 6

lonelyNumber([3, 3, 9])
// 9

Constraints

  • Length of the array <= 100000
  • The values of the array will be between -1000000000 and 1000000000

You can see the full challenge with visuals at this link.

Challenges • Asked almost 2 years ago by Anonymous

Jake from AlgoDaily Commented on Aug 12, 2019:

This is the main discussion thread generated for Lonely Number.

Anonymous Commented on Aug 12, 2019:

Using delete on an object does not appear to work as intended. Running with an odd number of multiple appearances, like console.log(lonelyNumber([4, 4, 6, 1, 1, 3, 1, 3])); returns 1 instead of the expected 6. I could not reduce the problem beyond setting to true or false if more than one, and then finding the first key with value of true. There is no built in method for this and it is potentially slow (?).

Jake from AlgoDaily Commented on Nov 19, 2019:

Hi,

Your example has 1 appearing 3 times, so the 3rd time, it gets added back to the array.

I've added a note: "Note that this only works if the rest of the numbers show up an even number of times. This is because if a number shows up three or more times, you'll end up adding it back to the hash map."

Anonymous Commented on Jan 09, 2020:

[deleted]

Tonya Sims Commented on Feb 19, 2020:

What about using the count function? Isn't it still 0(n)?

def lonely_number2(arr):
for item in arr:
if arr.count(item) == 1:
return item

Anonymous Commented on Mar 25, 2020:

[deleted]

Jacob Danner Commented on Jan 02, 2021:

This was the most helpful explanation of XOR I've read, still not sure I'd pull this out in an interview but it makes this bitwise operations seem much more accessible! Thanks!

Jake from AlgoDaily Commented on Jan 02, 2021:

So happy to hear that, Jacob :-) Check out https://algodaily.com/lessons/bitwise-operators-and-bit-manipulation-for-interviews for even more fun with bit manipulation!

Vits94 Commented on Feb 18, 2021:

How about using Math to solve the problem:-
Idea -> 2 * (a + b + c) - (a + a + b + b + c) = c

Code:
public int lonelyNumber(int[] nums) {
int sumOfNums = 0, sumOfSet = 0;
Set s = new HashSet<>();

for(int x : nums) {
if (!s.contains(x)) {
s.add(x);
sumOfSet += x; // set will contain only unique elements from given array
}
sumOfNums += x;
}
return 2 * sumOfSet - sumOfNums;

}