Oh man, I've spend few hours on this problem even though I had idea how to solve it after 10-15 minutes...
Those corner cases killed me... :)
[OPINION] Some of the problems on Hackerrank are not for cracking the coding interview or teaching you a cool new way of thinking but rather for testing your patience and corner case engineering abilities. This is one of those problems. The return of investment in that kind of problems is very low. At least the author could make the special cases in inputs more obvious by making them concise to save us some debugging time.
Is all the cases right? If the num is 110, then the next number should be 1001.
In TC#8, the case is
2
2 1Which represents 110. The next number with the same set-count is 1001, which is represented as
1 2 1.But the expected output is 1 3 1.
Am I understanding this correctly?
Python 3
def whatsNext(arr): # set bits are at each even index l = len(arr) -1 # case: l == 0 if not l: if arr[0] == 1: print(2) print(*[1, 1]) else: print(3) print(*[1, 1, arr[0]-1]) return # find index for least significant set bit i = l-1 if l & 1 else l # case: l == 1 if l == 1: t = [1, arr[1] +1, arr[0] -1] # case: last bit group is off elif l - i: t = arr[:i-1] + [arr[i-1] -1, 1, arr[-1] + 1, arr[i] -1] # case: last bit group is set else: t = arr[:i-1] + [arr[i-1] -1, 1, 1, arr[i] -1] # handle zeros if not t[-1]: t.pop(-1) if t.count(0): i_lst = [] for i,a in enumerate(t): if not a: # combine bits around zero t[i-1] += t[i+1] i_lst.append(i) # remove zero and extra bits for i in i_lst[-1:-1-len(i_lst):-1]: t.pop(i+1) t.pop(i) print(len(t)) print(*t)
Sort 39 Discussions, By:
Please Login in order to post a comment