CareerCup

Dumb way

package fb;

public class Flips {

	public static void main(String[] args) {
		int[] input = {0,0,0,0,0,1};
		int n = findMinimumFlips(input);
		System.out.println(n);
	}

	private static int findMinimumFlips(int[] input) {
		int rightflips = 0;
		for (int i = 1; i < input.length; i++) {
			rightflips = rightflips + input[i];
		}
		int leftflips = 1-input[0];
		int flips = rightflips+leftflips;
		for (int i = 1; i < input.length-1; i++) {
			if (input[i] == 1) {
				rightflips -=1;
			} else {
				leftflips+=1;
			}
			if (flips>rightflips+leftflips) {
				flips = rightflips+leftflips;
			}
		}
		return flips;
	}
}

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;
}

@Alex can you please explain your logic here ?

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);
}

1) Have two pointers left = 0 and right = str.length -1
2) left searches for zero and right searches for one
3) if (left < right) swap/switch and increment counter by 2
4) repeat 2-3 until left < right and return counter

@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.

@Phoenix. We don't have to keep constant number of zeros and ones in the bit array. So, we have more freedom in making less flips. E.g. for the example of this task:
1011000 -> 1111000,
your algorithm would produce 2 flips.

It is not just:
-- Count the number of '1' --> numberOf1s
-- Count the numbers of 1' in array[numberOf1s, array.length-numberOf1s] --> flipCount
-- return 2*flipCount ( for every 1 we flip, we need to flip a 0 )

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

Its a bit unclear, why would 00001 --> 10000 require 2 flips? Is 00000 (1 flip) not an acceptable answer? The question doesn't require you the preserve number of 1s. It just asks for min flips.

@dora. Yes, the description looks a bit inconsistent. E.g. in Example 1 the amount of ones is not preserved: 1011000 -> 1111000 only need one flip 0 -> 1.

Find the position for the last 1 with min number of flips required by counting the 0s from the left and 1s from the right. Return the smallest sum of the two

object FindMinFlip extends App {
  println(flips("0000001"))
  println(flips("1010001111010"))

  def flips(in: String): Int = {
    val count = Array.fill(in.length)(0)
    var i = 0
    var zerosToLeft = 0
    while (i < in.length) {
      if (in(i) == '0') {
        zerosToLeft += 1
      }
      count(i) = zerosToLeft
      i += 1
    }

    var onesToRight = 0
    i = in.length - 1
    while (i > 0) {
      i -= 1
      if (in(i + 1) == '1') {
        onesToRight += 1
      }
      count(i) += onesToRight
    }
    count.min
  }

}

public class NumberOfFlips {


    public static void main(String[] args) {
        System.out.println(findFlipCount("1000")==0);
        System.out.println(findFlipCount("00001")==2);
        System.out.println(findFlipCount("1011000")==1);
        System.out.println(findFlipCount("1011001")==2);
    }

    public static int findFlipCount(String input){
        int numOfOne = 0;
        int numOfZero = 0;

        int flips= 0;
        for(int i=0;i<input.length();i++){
            if(input.charAt(i) == '1'){
                numOfOne++;
            }else{
                numOfZero++;
            }
        }
        if(numOfOne == input.length()|| numOfZero == input.length()){
            return 0;
        }
            for(int k=1;k<=numOfOne;k++){
                if(input.charAt(k-1) == '0'){
                    flips++;
                    numOfZero--;
                }
            }
            for(int k=1;k<=numOfZero;k++){
                if(input.charAt(input.length()-k) == '1'){
                    flips++;
                }
            }
        return flips;
    }
}

public static void main(String[] args) {
        System.out.println(findFlipCount("1000")==0);
        System.out.println(findFlipCount("00001")==2);
        System.out.println(findFlipCount("1011000")==1);
        System.out.println(findFlipCount("1011001")==2);
    }

    public static int findFlipCount(String input){
        int numOfOne = 0;
        int numOfZero = 0;

        int flips= 0;
        for(int i=0;i<input.length();i++){
            if(input.charAt(i) == '1'){
                numOfOne++;
            }else{
                numOfZero++;
            }
        }
        if(numOfOne == input.length()|| numOfZero == input.length()){
            return 0;
        }
            for(int k=1;k<=numOfOne;k++){
                if(input.charAt(k-1) == '0'){
                    flips++;
                    numOfZero--;
                }
            }
            for(int k=1;k<=numOfZero;k++){
                if(input.charAt(input.length()-k) == '1'){
                    flips++;
                }
            }
        return flips;
    }

It is very easy

public int findMiniFlip(int[] nums){
	if (nums[0]==1) return 1;// covers 1011000 case
	if (nums[1]==0) return 2;// covers 00001 case
}