1
$\begingroup$

My question is about LeetCode "137.Single Number II":

137.Single Number II

Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Is there a generalized way to solve this and similar questions with the minimum number of bit-wise operations? By similar questions, I mean finding a number that appears k' times where other numbers appear k times.

More detail:

To solve this, I implemented a counter such that bit i of the counter becomes 1 only when 1 appears 3k+1 times in bit i of nums. To do so, I used two integers, A and B, to keep the 1 bit count for each bit i. I wrote down a possible sequence for bits in A and B so I could use A as the counter (there were possible other sequences): AiBi = 00 -> 10 -> 01 -> 00 -> .... Then, I used a similar approach as calculating a Logic Gate to find bit operations that resulted in the above sequence:

Logic Gate calculation for bit operations that give the above sequence for A and B

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        A = 0 
        B = 0 
        for num in nums:
            A, B = ((~(A|B))&num)|(A&~num),(A&num)|(B&~num)
        return A

With the same approach, I can find any number that repeats k times if all other numbers repeat k' times.

Then I saw this solution:

class Solution:
  def singleNumber(self, nums: List[int]) -> int:
    ones = 0
    twos = 0

    for num in nums:
      ones ^= (num & ~twos)
      twos ^= (num & ~ones)

    return ones

This is more efficient and beautiful than mine because it does 6 bitwise operations per num; mine does 10. What is the most efficient way to implement such counter? How could I know mine was not efficient?

$\endgroup$

1 Answer 1

1
$\begingroup$

It's hard to find the exact optimal sequence of instructions to accomplish some effect. I don't know of any systematic way, other than techniques like superoptimization, which essentially do a brute-force search over all possibilities.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.