Flip bits in a range and print number of ‘1’s

http://churmura.com/algorithms/vmware-online-coding-test-for-us-recruitments-hyderabad-event/69549/

/* Copyleft: Ming Lin <minggr@gmail.com> */

#include <stdio.h>

int count[100][100];

int flip_bits(int data[], int n)
{
	int len, i, j;
	int max = -1;
	int bits = 0;

	for (i = 0; i < n; i++)
		if (data[i] == 1)
			bits++;

	for (len = 1; len <= n; len++) {
		for (i = 0; i <= n-len; i++) {
			j = i+len-1;
			if (len == 1) {
				if (data[j] == 0)
					count[i][j] = bits + 1;
				else
					count[i][j] = bits - 1;
			} else {
				if (data[j] == 0)
					count[i][j] = count[i][j-1] + 1; 
				else
					count[i][j] = count[i][j-1] - 1; 
			}

			//printf("count[%d][%d]: %d\n", i, j, count[i][j]);
				
			if (max == -1 || count[i][j] > max)
				max =  count[i][j];
		}
	}

	return max;
}

int main()
{
	int data[] = {1, 0, 0, 1, 0, 0, 1, 0};
	int n = 8;

	printf("%d\n", flip_bits(data, n));

	return 0;
}

 

Leave a Reply