## Facebook Interview Question

SDE1s**Country:**United States

Possible solution with O(N) time complexity (where N - number of bits) and O(N) memory complexity:

- Calculate how many flips of '0' need to be done when you move from left to right to have all '1' in bits

- Calculate how many flips of '1' need to be done when you move from right to left to have all '0' in bits

- Walk through all positions between bits and find minimal sum of '0'-flips+'1'-flips from both arrays:

```
private static int minimalFilps(String bits) {
int flipsFromLeft[] = new int[bits.length()];
int flipsFromRight[]= new int[bits.length()];
int flips=0;
for(int i=0;i<bits.length();i++) {
if(bits.charAt(i)=='0') {
flips++;
}
flipsFromLeft[i]=flips;
}
flips=0;
for(int i=bits.length()-1;i>=0;i--) {
if(bits.charAt(i)=='1') {
flips++;
}
flipsFromRight[i]=flips;
}
int minFlips=Integer.MAX_VALUE;
for(int i=1;i<bits.length();i++) {
if(flipsFromLeft[i-1]+flipsFromRight[i] < minFlips)
minFlips=flipsFromLeft[i-1]+flipsFromRight[i];
}
return minFlips;
}
private static void doTest(String bits, int expectedFlips) {
int minFlips = minimalFilps(bits);
System.out.println(String.format("%s\t%d\t%d",bits, expectedFlips, minFlips));
}
private static void bulkTest() {
Map<String, Integer> tests = new LinkedHashMap<String, Integer>() {{
put("1000",0);
put("0001",2);
put("1001",1);
put("1011001",2);
put("10110000",1);
}};
System.out.println("Bits\tExpected\tActual");
for(Map.Entry<String, Integer> test : tests.entrySet())
doTest(test.getKey(), test.getValue());
}
public static void main(String[] args) {
bulkTest();
}
```

Could be solved using dynamic programming. Here's a quick Python example:

```
def minflip(b, index=0, all_flips=None, num_flips=0):
# Lazy init all_flips to keep track of possible flip solutions
if all_flips == None:
all_flips = {} # dict { num_flips: binary_array }
for i in range(index, len(b)):
if i == 0 and b[0] == 0: # make sure first bit is always 1
b[0] = 1
else:
# break if there's only zeros to the right
terminate = True
for j in range(i, len(b)):
if b[j] == 1:
terminate = False
if terminate:
break
# Try solution without flip recursively
minflip(b[:], i+1, all_flips, num_flips)
# Flip bit no matter what
b[i] = 1 if b[i] == 0 else 0
num_flips += 1
# Discard solution if the 1s on the left, 0s on the right constraint does not hold
discard = False
for i in range(1, len(b)):
if b[i-1] == 0 and b[i] == 1:
discard = True
if b[-1] == 1: # Discard if last bit is 1
discard = True
if not discard:
all_flips[num_flips] = b
if len(all_flips) > 0:
min_flips = min(all_flips.keys())
return all_flips[min_flips], min_flips # Return the minimum flip solution
return None
print(minflip([0,0,0,0,1]))
print(minflip([1,0,1,1,1,0,0,0]))
```

Time complexity should be O(n^2).

O(n) + k soln. -

```
public static void main(String[] args){
int[] nums = {0,0,0,0,1};
int n = findMiniFlip(nums);
System.out.println(n);
}
//1011000; 00001
public static int findMiniFlip(int[] nums) {
int n = nums.length;
String s = "";
for(int i = 0; i < n; i++)
s += nums[i];
long num = Integer.parseInt(s, 2);
int minXor = n;
long mask = (1<<(n-1));
while(n-1 > 0){
long temp = (num ^ mask);
minXor = Math.min(minXor, countones(temp));
n--;
mask = (mask | (1<<n));
}
return minXor;
}
public static int countones(long n){
int c = 0;
while(n > 0){
n = n & (n-1);
c++;
}
return c;
}
```

O(n) time and space.

```
#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;
int MinFlipsCount(uint8_t const *a, int size, unordered_map<uint64_t, int> &memo, int prev = 1, int idx = 0)
{
if (idx < 0 ||
idx > size)
{
return -1;
}
if (idx == size) {
return 0;
}
uint64_t memo_key = (static_cast<uint64_t>(idx) << 32) | prev;
auto it = memo.find(memo_key);
if (it != memo.end()) {
return it->second;
}
int bit = ((a[idx >> 3] & (1 << (7 - (idx % 8)))) == 0) ? 0 : 1;
int flip_to_zero_count = numeric_limits<int>::max();
int flip_to_one_count = numeric_limits<int>::max();
if (idx != 0) {
flip_to_zero_count = (bit == 0 ? 0 : 1) + MinFlipsCount(a, size, memo, 0, idx + 1);
}
if (idx != size - 1 &&
prev == 1)
{
flip_to_one_count = (bit == 1 ? 0 : 1) + MinFlipsCount(a, size, memo, 1, idx + 1);
}
memo[memo_key] = min(flip_to_zero_count, flip_to_one_count);
return memo[memo_key];
}
int main () {
vector<pair<uint8_t, int>> bit_arrays = {
{0b10110000, 7},
{0b10110000, 7},
{0b00001000, 5},
{0b10101010, 8},
{0b00001111, 8},
{0b10011100, 8},
{0b10111111, 8},
};
for (auto el : bit_arrays) {
unordered_map<uint64_t, int> memo;
cout << MinFlipsCount(&el.first, el.second, memo) << "\n";
}
return 0;
}
```

var num = "1011000";

findMiniFlip(num);

function findMiniFlip(num) {

var arr = num.split("");

arr = arr.map(item => {

return new Number(item);

});

var flips = 0;

if(arr[0] != 1){

arr[0] = 1;

flips ++;

}

if(arr[arr.length - 1] != 0){

arr[arr.length - 1] = 0;

flips ++;

}

var indexFlip = [];

arr.forEach((item, index) => {

if(index != 0 && index != arr.length - 1 &&

!indexFlip.find(item => { return item == index})){

if(item == 1 && arr[index - 1] == 0){

indexFlip.push(index - 1);

flips ++;

}

else if (item == 0 && arr[index + 1] == 1) {

indexFlip.push(index + 1);

flips ++;

}

}

});

console.log(flips);

}

@Anonymous. At each position, we just try to flip to 0 and see how many flips are needed for the rest of the bits. And at the same position we also try to flip to 1 and see how many flips are needed for the rest of the bits. And we choose minimum from the two flip counts. Also, we use memoization to optimize time.

```
int findMinFlip(vector<int>& binary)
{
size_t count = 0, last_left = -1, last_right = -1;
size_t left = 0, right = binary.size() - 1;
for (; left < right; ) {
if (binary[left] == 0)
last_left = left;
else if (last_left != -1 && last_left != left) {
count += left - last_left;
last_left = -1;
}
if (binary[right] == 1)
last_right = right;
else if (last_right != -1 && last_right != right) {
count += last_right - right;
last_right = -1;
}
left++;
right--;
}
if (last_left != -1 && last_left != left) {
count += left - last_left;
last_left = left;
}
if (last_right != -1 && last_right != right) {
count += last_right - right;
last_right = right;
}
return count;
}
```

```
'''
F(i) =
if A[i] == 0:
min(1 + F(i + 1), N1[i + 1])
else:
min(1 + N0[i + 1], F(i + 1))
F(n - 1) = 0
N0[i]: number of 0's in A[i:]
N1[i]: number of 1's in A[i:]
Bottom-up DP complexity:
Time: O(n)
Space: O(1)
'''
from itertools import accumulate, islice
def solution(binary_array):
n = len(binary_array)
if n <= 1:
return 0
N0 = accumulate([1 - bit for bit in binary_array[::-1]])
N1 = accumulate(binary_array[::-1])
f = 0
for n0, n1, i in zip(N0, N1, range(n - 1, -1, -1)):
bit = binary_array[i]
if bit == 0:
f = min(1 + f, n1)
else:
f = min(1 + n0, f)
return f
A = [1, 1, 0, 1, 0, 0, 0, 1, 0]
attempt = solution(A)
print(attempt)
assert attempt == 2
A = [0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1]
attempt = solution(A)
print(attempt)
assert attempt == 5
A = [1, 0, 1, 1, 0, 0, 0]
attempt = solution(A)
print(attempt)
assert attempt == 1
```

Dumb way

- den.zvon November 09, 2017