Счастливые билетики до 300 цифр

Началось все с тестового задания на вакансию «js-developer, Node.js-developer», и тут я выпал в осадок: задача на счастливые билетики.

Посчитать количество счастливых билетиков для 2, 4, 6, 8 и 10 цифрового значения.

Уверен, многие уже не раз делали эту банальную задачку, но, как правило, для 6-ти цифр (для тех, кто не понимает о чем пойдет речь).

Банальное решение:

var
	sum = function(num){ // функция для получения суммы цифр
		var
			str = num.toString(),
			arr = str.split(''),
			s = 0;
		arr.forEach(function(value){ s+=parseInt(value); });
		return s;
	},
	luckyTickets = function(len){
		var
			lenMiddle = len/2,
			maxSize = Math.pow(10,lenMiddle),
			result = 0;
			for(var i=0;i<maxSize;i++)
				for(j=0;j<maxSize;j++)
					if( sum(i) == sum(j) ) result++;
			return result;
	};

	console.log( luckyTickets(8) ); //  4 816 030

Также можно посмотреть тут.

А если цифр 10? 30? 200? Беда! Приходиться ооочень долго ждать результата: аналог в PHP (5.3) «умирал», даже когда я давал 10 цифр и set_time_limit (3600).

Теперь вернемся в мир JS. Несмотря на то, что простые циклы в Node.js выполняются быстрей, чем в PHP, время выполнения меня все равно не устраивало (1 029 458 ms).

А теперь хватит этого унылого текста, переходим к альтернативному решению.

Сама зацепка оказалась в журнале «Квант», № 12 (1976), с.68–70 (электронный вариант ).

Там же можно увидеть вывод — таблица, с помощью которой можно легко узнать «количество счастья» в билетах из 2 (n=1), 4 (n=2), 6 (n=3) и 8 (n=4) цифрами.

Как заполнить таблицу — изображено ниже:



То есть сумма 10 элементов предыдущего столбца, у которых индекс <= нужному значению. Количество счастливых билетов равно сумме каждого значения в квадрате в определенном столбце:

— для n=1 (2 цифры) -> 1^2 + 1^2 +… + 1^2 = 10;
— для n=2 (4 цифры) -> 1^2 + 2^2 +… + 1^2 = 670;
— для n=3 (6 цифр) -> 1^2 + 3^2 +… + 75^2 +… + 1^2 = 55 252;
— для n=4 (8 цифр) -> 1^2 + 3^2 +… + 670^2 +… + 1^2 = 4 816 030;

Дальше наш ход.

var
	getNextArr = function(prevArr){ // функция для построения следующего массива из предыдущего
		var 
			newLen =  prevArr.length + 9, // длинна следующего массива будет больше на 9
			arr = []; // заготовка результата
		for(var i=0; i<newLen; i++){
			var q = 0; // заготовка нового значения
			for(j=0; j<10; j++) // берем 10 нужных значений
				if(prevArr[i-j]) // ...если они существуют в предыдущем массиве
					q+=prevArr[i-j]; // добавляем
			arr[i] = q; // или arr.push(q);
		}
		return arr;
	},
	luckyTickets = function(num){ // собственно сам  счетчик
		var
			arr = [], // первый массив
			result = 0; // то, что мы вернем
		for(i=0;i<10;i++) arr.push(1); // впихиваем в первый массив 10 единиц
		for(i=0;i<(num/2-1);i++) // нужное количество раз
			arr = getNextArr(arr); // строим следующие массивы
		arr.forEach(function(v){ result+=Math.pow(v,2); }); // сводим квадраты значений в получившемся массиве
		return result;
	};

Ну и проверить же нужно:

console.log( luckyTickets(300) ); // 8.014950093120178e+297 **

Собственно то, к чему все велось: время выполнения 106 ms (!!!), страшно представить, что бы случилось при использовании банального способа.

* все JavaScript-ы проверял на Node.js (x32)
** максимальная длинна номера билета — 310, Больше? — результат переходит в область Infinity.
*** это моя первая статья на Хабре за последние 3 года, прошу камнями не бросать.