CareerCup

The approach is simple:
match the head and for the tail do a swap for desired character to left.

I could not prove it would be lease

#include <iostream>
#include <map>
#include <cstring>
using namespace std;

void swap(char * convert , int j)
{
	char temp = convert[j];
	convert[j] = convert[j-1];
	convert[j-1] = temp;
}

int transformCost(char * master, char * convert , int i)
{
	int matchcounter = 0;
	int cost = 0;
	while(matchcounter < i)
	{
		if(master[matchcounter] == convert[matchcounter])
		{
			matchcounter++;
			continue;
		}
		char m = master[matchcounter];
		bool found = false;
		int matchpos = -1;
		for(int j = matchcounter ; j < i; j++)
		{
			if(convert[j] == m)
			{
				matchpos = j;
				found = true;
				break;
			}
		}
		if(found)
		{
			swap(convert,matchpos);
			cost++;
		}
		else
		{
			return -1;
		}
	}
	cout<<"Master  : " << master<<endl;
	cout<<"Convert : " << convert<<endl;
	return cost;
}


int main()
{
	char a[] = "101010101010";
	char b[] = "111111000000";
	cout<<transformCost(a,b, strlen(a))<<endl;
	return 0;
}

int SwapCount(int A[], int B[], int size)
{
	int j = 0;
	int minSwapCount = 0;
	for(int i =0; i < size; i++)
	{
		if(A[i] == 1)
		{
			
			while(B[j] !=1)
			{
				j++;
			}
			if(i > j)
				minSwapCount += i - j;
			else
				minSwapCount += j - i;
			j++;
		}
	}

	return minSwapCount;

}
int main()
{
	int A[] = {1,0,0,1};
	int B[] = {0,1,1,0};
	printf("SwapCount = %d", SwapCount(9, 6));
	return 0;
}

int minSwaps(int A[], int B[], int n)
{
	assert(A != NULL && B != NULL && n > 0);

	int ans = 0, rb = 1;

	for (int i = 0; i < n; ++i)
	{
		if (A[i] != B[i])
		{
			if (rb <= i) rb = i + 1;

			while (rb < n && A[rb] != B[i]) ++rb;

			if (rb >= n) throw logic_error("there is no solution");

			ans += rb - i; A[rb] = A[i]; ++rb;
		}
	}

	return ans;
}

void findMInSwapBinary(int binArr1[n],int binArr2[n])
{
	int minSwaps =0;
	for(int i=0;i<n;i++)
	{
		if(binArr1[i] ^ binArr2[i]==1)
			minSwaps++;
	}
	return;
}

void findMInSwapBinary(int binArr1[n],int binArr2[n])
{
	int minSwaps =0;
	for(int i=0;i<n;i++)
	{
		if(binArr1[i] ^ binArr2[i]==1)
			minSwaps++;
	}
	return;

}

XOR the numbers, then see how many 1s there are in this value

Reasoning:
We know that a ^ a = 0 , so 1 ^ 1 = 0 and 0 ^ 0 = 0
But, 1 ^ 0 = 1 and 0 ^1 = 1, so we see that we can find differences by xoring


Some code:

int numSwaps(int a, int b) {
	
	int c = a ^ b;
	int output = 0;

	while (c != 0) {

		out += c & 1;
		c =>> 1;
	}

	return out;
}

This one works, but given the answer size there might be an easier solution or this is not an interview question.

public static void main(String[] args) throws Exception {
        Random rseed = new Random();
        int seed = rseed.nextInt(100);
        System.out.println("seed = " + seed);
        Random r = new Random(seed);
        int size = 10;
        int[] orig;
        int[] dest = new int[size];
        for (int i = 0; i < dest.length; i++) {
            dest[i] = r.nextInt(3)==1? 1 : 0;
        }
        orig = dest.clone();
        for (int i = 0; i < dest.length-1; i++) {
            int tmp = orig[i];
            int destIndx = i + r.nextInt(size-i-1);
            orig[i] = orig[destIndx];
            orig[destIndx] = tmp;
        }

//        orig = new int[]{1, 0, 0, 0, 1, 0, 0, 0, 0, 1};
//        dest = new int[]{0, 0, 0, 0, 0, 1, 0, 1, 0, 1};

        System.out.println("Orig" + Arrays.toString(orig));
        System.out.println("Dest"+Arrays.toString(dest));
        System.out.println();
        System.out.println("Best "+findMinSwaps(orig, dest));


    }

    private static int findMinSwaps(int[] orig, int[] dest) throws Exception {
        int leftDest=0,
                leftOrigin=0,
                rightOrigin=orig.length-1,
                rightDest=orig.length-1;

        int swaps = 0;
        while(!Arrays.equals(orig,dest)){
            //scan left to right
            while(leftDest < dest.length && (dest[leftDest]==0 || orig[leftDest]==1) )
                leftDest++;
            while(leftOrigin< orig.length && (orig[leftOrigin]==0 || dest[leftOrigin]==1))
                leftOrigin++;
            if(leftDest != dest.length-1 && leftOrigin != dest.length-1 )
                swaps+= multipleSwaps(orig,leftOrigin,leftDest);

            //scan right to left
            while(rightDest>0 && (dest[rightDest]==0 || orig[rightDest]==1))
                rightDest--;
            while(rightOrigin>0 && (orig[rightOrigin]==0 || dest[rightOrigin]==1) )
                rightOrigin--;
            if(rightDest != 0 && rightOrigin != 0)
                swaps+= multipleSwaps(orig,rightOrigin,rightDest);

            leftDest++;
            leftOrigin++;
            rightDest--;
            rightOrigin--;
        }
        return swaps;
    }

    private static int multipleSwaps(int[] orig, int from, int to) throws Exception {
        if(from == to)
            return 0;
        int direCtion = (to-from)/Math.abs(to-from);
        int swaps =0;
        while(from != to){
            if(orig[from+direCtion]==1){
                swaps+=multipleSwaps(orig,from+direCtion,to);
                swap(orig,from,from+direCtion);
                System.out.println("Orig" +Arrays.toString(orig));
                return swaps+1;
            } else {
                swap(orig,from,from+direCtion);
                System.out.println("Orig" +Arrays.toString(orig));
                from+=direCtion;
                swaps++;
            }
        }
        return swaps;
    }


    static void swap(int[] data, int indx1, int indx2) throws Exception {
        if(Math.abs(indx1-indx2)!= 1)
            throw new Exception("Wrong indexes " + indx1 + " " + indx2);
        int tmp = data[indx1];
        data[indx1] = data[indx2];
        data[indx2] = tmp;
    }