bowl
BAN USERdef has_redundant(s):
stack = [0]
for c in s:
if c == '(':
stack.append(0)
elif c == ')':
if stack.pop() == 0:
return True
else:
stack[-1] += 1
# Treat (expr) as redundant
return stack.pop() == 0
assert has_redundant("()")
assert has_redundant("(a+b)")
assert not has_redundant("(a+b)+c")
assert has_redundant("((a+b))+c")
O(number of braces) space, O(n) time
Assuming that braces are balanced.
Let's count the number of 1's on each position in binary representation.
So if the numbers are
3 5 3 3
which is
011 101 011 011
in binary
The corresponding counters will be
{1, 3, 4}
Every number repeats 3 times, so let's take each counter modulo 3 to clean the 3-times-repeating elements.
{1, 0, 1}
this is the number which is unique.
Now what we have to do is just count the number of 1's at each position modulo 3
We need a 2-bit counter for every bit position that will increment every time it meets a number with the corresponding bit is set.
It increments like this: 00 -> 01 -> 10 -> 00 (since we need modulo 3)
We store lower bit and higher bit of counters in counter_lower and counter_higher
Then we just do the following
For every bit position where number bit is set and both counter bits are 0, change the lower counter from 0 to 1 (this is 00 -> 01 transition
For every bit position where number bit is set and lower counter is set, set the lower counter bit to zero and higher counter bit to 1 (01 -> 10 transition)
For ... where higher counter bit is set, just unset the higher counter bit (10 -> 00 transition)
That's all, after we've processed all numbers, we will have our unique number in lower counter.
This is the same logic for "find a unique element in array where every other element is met twice" - here when we xor, our accumulator is 1-bit counter. In this problem we just switch from 1-bit counters to 2-bit counters
It's up to conventions, whether we count bitwise operation of two numbers as O(1) or O(log(b)) where b is the number of bits in number.
- bowl November 04, 2014It's commonly assumed that if we add two int32 it's O(1) and if we iterate over bits of int32 it's O(log(b)).