natural_seq_check.js

var good = [
	[1,2,3,4,5,6,7,8],
	[1,2,8,4,5,6,7,3],
	[1,5,8,4,2,6,7,3]
];
var bad = [
	[1,2,3,6,5,6,7,6],
	[1,2,3,4,5,6,8],
	[1,2,3,4,5,6,7,8,10]
];

// O(n*logn)
function isNaturalSequence (seq) {
	var n = seq.length;
	var digits = new Array(Math.ceil(Math.log2(n)) + 1);
	for (var i = 0; i < digits.length; i++) { digits[i] = 0; }
	seq.forEach(function(num) {
		for (var i = 0; i < digits.length; i++) {
			digits[i] += num & (1 << i) ? 1 : 0;
		}
	});
	for (var i = 0; i < digits.length; i++) {
		var count = digits[i];
		var period = Math.pow(2, i);
		var x = n - (period - 1);
		var periods = Math.floor(x / period);
		var expectedCount = periods % 2 == 0
			? (periods/2 * period + (x % period))
			: ((Math.floor(periods/2) + 1) * period);
		if (expectedCount !== count) {
			return false;
		}
	}
	return true;
}

// O(n)
function isNaturalSequence (seq) {
	var newSeq = seq.slice(0);
	var i = 0;
	var k = 0;
	while (i < newSeq.length) {
		if (k > newSeq.length) {
			return false;
		}
		if (newSeq[i] === (i + 1)) {
			i++;
			k = 0;
		}
		else {
			k++;
			var ind = newSeq[i] - 1;
			var t = newSeq[ind];
			newSeq[ind] = ind + 1;
			newSeq[i] = t;
		}
	}
	return true;
}

console.log(good.every(isNaturalSequence) === true ? 'correct for good sequences' : 'incorrect for good sequences');
console.log(bad.some(isNaturalSequence) === false ? 'correct for bad sequences' : 'incorrect for bad sequences');