Find non-duplicated integer

Question

Given an array of integers where every integer occurs three times except for one integer, which only occurs once, find and return the non-duplicated integer.

For example, given [6, 1, 3, 3, 3, 6, 6], return 1. Given [13, 19, 13, 13], return 19.

Do this in O(N) time and O(1) space.

Answer 1

I really love that solution, lion ! It's short, simple, and wickedly clever! Now, could you please help me analyze the complexities?

Time complexity (in terms of operations performed): O(n),

Bit complexity: As n increases, the maximum number in the array increases linearly (we can only repeat twice). As an integer i increases, 4^i increases exponentially, and hence so does your s. As s increases, time taken to perform bitwise AND on it increases logarithmically (right?). So each operation seems to be linear in n, and the bit complexity O(n^2). By this logic, my technique would probably be O(n log n).

Space complexity: Your s is large. You're basically treating it as Boolean array that stores information on the integer i at position 2i (and 2i+1). (In that sense, it's not all that different from the dictionary based solution.) I imagine as an integer gets big, even Python would require more and more space to store it. So it could be more like O(n) memory, whereas mine should be an unavoidable O(log n).

Answer 2

Kishalaya Saha considering the max number, i found we often only think about time/space complexity relative to the list length, but it seems that it should be the whole size🤔

Answer 3

I'd probably use a dictionary. Iterate through and set each int to a key and increment the corresponding value as each integer is visited. At the end, print the key with a value of 1.

Not sure if an easier method exists, but this is my first instinct.

Answer 4

Benjamin's algorithm works, but it takes O(n) space.

If you want O(1) space, the only thing I can think of is using a handmade bitwise operator: it'd be like the bitwise XOR, except for each bit, it'd give a zero when it sees three 1s.
In other words, we're adding the digits, but with modulo 3.

If that sounds too complicated, first try a simpler variant where each array element except one is repeated twice. Then taking the bitwise XOR of all the elements would result in the answer.

Answer 5

Kishalaya Saha maybe find a function f which has property f(f(f(x))) = 0 or f(f(f(x))) = 1🤔

Answer 6

Not sure if it's time O(n), space O(1)🤔
They depend on the max number🤔
https://code.sololearn.com/c3BSGRy6U41D

Answer 7

Okay, thanks so much lion. I'm not very confident about complexity calculations.

And I really liked your trick! I'll have to remember it in future. Bit operations are so cool sometimes!

And good point, Flandre Scarlet . It would make sense to define it that way.

Answer 8

lion I believe your code will fail for negative integers.

Answer 9

If you need help with the problem, please share your attempt first! Thank you!

Answer 10

Good point on space usage and good idea for a remedy. Otherwise I am still pondering achieving O(1).

Answer 11

you're both right, it only _looks_ like that, and only in python :) For big numbers it would take MUCH more space than a dictionary, the given example already takes more than 20k bits while a dictionary would only take about O(n/3) space.

Answer 12

Mayur Garg thx, I didn't think of that :)
Anyway, after I googled that O(1) means constant space, not necessarily 1, I made another one by Kishalaya's suggestion, which also doesn't work with negative numbers, but is closer to the requirement:
https://code.sololearn.com/cjdEmW97d8eK/?ref=app

Answer 13

Spoiler:
I too was googling about some stuff regarding this question and somehow stumbled upon the same question at Geeks4Geeks containing multiple possible solutions. There is a link below. Open it only if you don't wish to attempt the question yourself.

https://www.geeksforgeeks.org/find-the-element-that-appears-once/

(However I think the last solution using Python sets is wrong as the size of that set won't be constant and will scale with 'n' which isn't what we need)

Answer 14

Mayur Garg Ha, I actually tried xor'ing using two variables, but I didn’t do it right and I thought it won't get me anywhere, so I came back to the idea that I posted :) I need to sleep now, but I'll have to think about it myself, now that I know the idea works (the solution is there, on one of the pages linked, but I want to concoct it myself, not just understand the one already written)

Answer 15

Ok, I slept on it and here it is:
https://code.sololearn.com/cTV2SC2mXvvo

Answer 16

Please post here only questions, no challenges!

Answer 17

https://code.sololearn.com/cC7G3T10SZmx/?ref=app

Answer 18

I guess this can be considered O(n) and O(1) only in Python:
https://code.sololearn.com/c8GzWca2FPcB/