Question: https://oj.leetcode.com/problems/single-number-ii/
Question Name: Single Number II
Follow Up: Every element appears N times except one for M time (N != M):
If N > M:
- If N % M == 0: use dictionary to count the appearance;
- If N % M != 0: similar with our solution, but change “(bitsResult[index] % N) << index” to “((bitsResult[index] % N) << index) // M”.
If N < M:
- If M % N == 0: use dictionary to count the appearance;
- if M % N != 0: let M = M % N, jump to the case N > M.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | class Solution: # @param A, a list of integer # @return an integer def singleNumber(self, A): # Ohhhhhh~ If it is set to 64, time out! BITS_IN_INTEGER = 32 bitsResult = [0] * BITS_IN_INTEGER # http://stackoverflow.com/questions/538551/handling-very-large-numbers-in-python # "interpreter will automatically use whichever is more appropriate." # http://stackoverflow.com/questions/7822956/how-to-convert-negative-integer-value-to-hex-in-python # "Python's integers can grow arbitrarily large" ... " with data type long" # # So setting the 31th bit to 1 cannot make it to be a negative number. # We have to track on how much negative integers are there. numberOfNegative = 0 for item in A: if item < 0: item = -item numberOfNegative += 1 for index in xrange(BITS_IN_INTEGER): # (item & (1<<index)) >> index would be either 1 or 0. bitsResult[index] += (item & (1<<index)) >> index result = 0 for index in xrange(BITS_IN_INTEGER): # (bitsResult[index] % 3) will be 1 or 0. result |= (bitsResult[index] % 3) << index # The single number is negative. if numberOfNegative % 3 != 0: result = -result return result |
Here is another solution for the prob from leetcode
Analysis from this blog post : http://traceformula.blogspot.com/2015/08/single-number-ii-how-to-come-up-with.html
Great details. Great blog!