#include <stdio.h>
#include <stdlib.h>

#define min(a, b)	(a < b ? a : b)

int check_property(int *row, int iL, int iR) {
	int	k, res, resl, resr;
	int	iM = (iR - iL) / 2;

	printf("check_property(%p, %d, %d) row[%d]=%d, row[%d]=%d\n",
	    row, iL, iR, iL, row[iL], iR, row[iR]);
	if (iM == 0) {
		printf("check_property(%p, %d, %d) returning %d\n",
		    row, iL, iR, row[iL] == row[iR]);
		return(row[iL] == row[iR]);
	}
	for (res = 1, k = 0; k < (iR-iL); k++) {
		if (row[iL + k] != row[iL + k + 1]) {
			res = 0;
			break;
		}
	}
	resl = check_property(row, iL, iL + iM);
	resr = check_property(row, iL + iM+1, iR);
	printf("check_property(%p, %d, %d) returning %d\n",
	    row, iL, iR, res + min(resl,resr));
	return(res+min(resl,resr));
}

/* Return 1 if N is a power of 2; otherwise, 0. */
/* Note that 1 is 2**0 and is a power of 2. */
int PowerOf2(int N) {
	int K = 1;
	while (K < N)
		/* Shift left one bit and multiply by 2 produce the same
		** results.
		*/
		K <<= 1;
	return(K == N);
}

int main(int argc, char *argv[]) {
	int	i,
		j,
		N,
		result = 0,
		**vec;

	if(argc < 2) {
		fprintf(stderr, "Usage: %s N\n", argv[0]);
		exit(1);
	}

	/* ... how many numbers to read */
	N = atoi(argv[1]);
	/* check if N is a power of two; exit if not */
	if(! PowerOf2(N)) {
		fprintf(stderr,
		    "%d is not a power of 2 as required.  Exiting.\n", N);
		exit(2);
	}

	/* Create array of N pointers to arrays of ints. */
	vet = (int**)malloc(N * sizeof(int*));
	if(vec == NULL) {
		fprintf (stderr, "ERROR: not enough memory available!\n");
		exit(3);
	}
	/* Now create N arrays of N ints. */
	for(i = 0; i < N; i++) {
		/* Note sizeof(int); not int* in following malloc(). */
		vec[i] = (int*)malloc(N * sizeof(int));
		if(vec[i] == NULL) {
			fprintf(stderr,
			    "ERROR: not enough memory available!\n");
			exit(3);
		}
	}

	for(i = 0; i < N; i++)
		for(j = 0; j < N; j++)
			scanf("%d", &vec[i][j]);

	printf("\nOriginal array:\n");  /* Trailing space removed from format.*/
	for(i = 0; i < N; i++) {
		for(j = 0; j < N; j++)
			printf("%d ", vec[i][j]);
		printf("\n");
	}

	/* Now process array; example below is to add numbers */
	/* Saying that check_property() adds numbers is not at all enlightening.
	** It seems to return 1 if all pairs of numbers on a row have the same
	** value (or if there is only one element on a row) and to return 0 if
	** one or more pairs of numbers on a row have different values.
	*/
	for(i = 0; i < N; i++) {
		printf("Processing row %d...\n", i);
		result = check_property(vec[i], 0, N-1);
		printf("result[row %d]: %d\n", i, result);
	}

	/* free memory */
	for(i = 0; i < N; i++)
		free(vec[i]);
	free(vec);

	exit(0);
}