a give number x 'good' if sum of 2 consecutive digit of number x between k , 2k. need find algorithm given number k , given number n, find how many 'good' n-digit numbers exist.
i made implementation in php, complexity big (i searching 'good' number , counting them, complexity o(10^n)).
<?php $n = 5; $k = 5; $min = $k*1; $max = $k*2; $counter = 0; ($i = pow(10, $n-1); $i<pow(10,$n); $i++) { $number = $i; $prev = $number % 10; $number = $number / 10; while($number >= 10) { $crnt = $number % 10; $number = $number / 10; if ( ($crnt+$prev) > $min , ($crnt+$prev) < $max ) { echo "good number: $i\n"; $counter++; } $prev = $crnt; } } echo "counter: ".$counter."\n"; ?> can confirm me if can solution:
n=100 // given k=10 // given counter = 0; for(i=10; i<100; i++) { if( (i/10)+(i%10) > k ) && ( (i/10)+(i%10) < 2*k ) counter++; } total = counter^(n-1)
all calls pow won't helping.
what can make mapping of two-digit numbers 'good'. once have mapping, need check every pair of digits in number good. can successive division 10 , modulo 100.
something trick, provided don't give negative number, , assuming you've set $good array.
function isgood( $num ) { while( $num >= 100 && $good[$num%100] ) { $num /= 10; } return $good[$num%100]; } the next obvious thing memoize larger sequences. dynamic programming principle. we've memoized small sequences storing 'goodness' of 2-digit sequences. use generate sequences of 3, 4, 5, 6 digits... whatever available memory allows. use memos have in order generate sequences 1 digit.
so, if built memoisation 5-digit numbers, divide 1000 every time, , great speedup.
Comments
Post a Comment