+ 2

Find non-duplicated integer

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.

3rd Nov 2018, 2:12 PM
Vasandakumar
Vasandakumar - avatar
18 Respostas
+ 5
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).
4th Nov 2018, 5:18 AM
Kishalaya Saha
Kishalaya Saha - avatar
+ 5
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šŸ¤”
4th Nov 2018, 5:57 AM
Flandre Scarlet
Flandre Scarlet - avatar
+ 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.
3rd Nov 2018, 3:00 PM
benjamin
+ 3
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.
3rd Nov 2018, 3:09 PM
Kishalaya Saha
Kishalaya Saha - avatar
+ 3
Kishalaya Saha maybe find a function f which has property f(f(f(x))) = 0 or f(f(f(x))) = 1šŸ¤”
4th Nov 2018, 1:47 AM
Flandre Scarlet
Flandre Scarlet - avatar
+ 3
Not sure if it's time O(n), space O(1)šŸ¤” They depend on the max numberšŸ¤” https://code.sololearn.com/c3BSGRy6U41D
4th Nov 2018, 4:15 AM
Flandre Scarlet
Flandre Scarlet - avatar
+ 3
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.
4th Nov 2018, 12:13 PM
Kishalaya Saha
Kishalaya Saha - avatar
+ 2
lion I believe your code will fail for negative integers.
4th Nov 2018, 12:42 PM
Mayur Garg
Mayur Garg - avatar
+ 1
If you need help with the problem, please share your attempt first! Thank you!
3rd Nov 2018, 2:52 PM
Kishalaya Saha
Kishalaya Saha - avatar
+ 1
Good point on space usage and good idea for a remedy. Otherwise I am still pondering achieving O(1).
3rd Nov 2018, 3:15 PM
benjamin
+ 1
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.
4th Nov 2018, 10:37 AM
lion
lion - avatar
+ 1
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
4th Nov 2018, 3:04 PM
lion
lion - avatar
+ 1
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)
4th Nov 2018, 3:28 PM
Mayur Garg
Mayur Garg - avatar
+ 1
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)
4th Nov 2018, 4:53 PM
lion
lion - avatar
+ 1
Ok, I slept on it and here it is: https://code.sololearn.com/cTV2SC2mXvvo
5th Nov 2018, 1:03 AM
lion
lion - avatar
0
Please post here only questions, no challenges!
3rd Nov 2018, 2:48 PM
ThƩophile
ThƩophile - avatar
3rd Nov 2018, 2:58 PM
Vasandakumar
Vasandakumar - avatar
0
I guess this can be considered O(n) and O(1) only in Python: https://code.sololearn.com/c8GzWca2FPcB/
4th Nov 2018, 2:39 AM
lion
lion - avatar