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).