MinMove

MinMoves.cpp

#include "pch.h"
#include <iostream>

void swap(int* a, int* b)
{
	int t = *a;
	*a = *b;
	*b = t;
}

void sort(int arr[], int asc, int& moves, int maxnumber, int n)
{
	int hitnumber = 0;
	for (int i = 0; i < n - 1; i++)
	{
		if (arr[i] != asc)
		{
			if (arr[i] != arr[i + 1])
			{
				swap(&arr[i], &arr[i + 1]);
				moves++;
				break;
			}
		}
	}

	for (int j = 0; j < maxnumber; j++)
	{
		if (arr[j] != asc)
			break;

		hitnumber++;
	}

	if (hitnumber == maxnumber)
		return;

	sort(arr, asc, moves, maxnumber, n);
}

int minMoves(int arr[], int n)
{
	int numberofone = 0;
	int onefactor = 0;
	int zerofactor = 0;
	for (int i = 0; i < n; i++)
	{
		if (arr[i])
		{
			numberofone++;
			onefactor += i;
		}
		else
		{
			zerofactor += i;
		}
	}

	bool isAsc = (onefactor >= zerofactor);

	int move = 0;
	sort(arr, isAsc ? 0 : 1, move, isAsc ? (n - numberofone) : numberofone, n);

	return move;
}

int main()
{
	int arr[] = { 0, 1, 0, 1, 1, 0, 1, 1 };
	int n = sizeof(arr) / sizeof(arr[0]);

	std::cout << "Moves : " << minMoves(arr, n) << std::endl;
	return 1;
}