Tuesday, July 12, 2016

max count of 1s by flipping one 0

//tests
1111
|--|4

1011
|--|4

 00
1001
||2
  ||2

0000
0000
||2
 ||2
  ||2
(n):
    maxcount1s = count1s = 0
    count0s = 0
    first0index = 0
    i = 31
    while i >= 0:
        if bit(n, i) == 0:
            count0s++
            if count0s == 2:
                if count1s > maxcount1s:
                    maxcount1s = count1s
                count1s = count0s = 0
                i = first0index -1
                continue
            else: // count0s == 1
                first0index = i
        count1s++
        i--
    if count1s > maxcount1s:
        maxcount1s = count1s
    return maxcount1s

bit(n, i):
    return (n >> i) &1
[Hat tip to ctci]

No comments:

Post a Comment