Example:

countOfOnes (12) = 5 1 - one 1 3 4 5 6 7 8 9 10 - two 1's 11 - four 1's 12 - five 1's

Since countOfOnes (1) = 1, they have requested to find the next number in which the parameter is equal to the return value of countOfOnes ( countOfOnes(n) = n ).

$ perl -e '$sum += () = /1/g for 1..shift; print "NumberOfOnes=$sum\n"' 111

NumberOfOnes=36

However, this solution was inefficient due to the high number of invocations needed to find the solution to the quiz.

So, analyzing the evolution of the mathematical calculation of the function numOfOnes, I outlined the following recursive algorithm:

Since, recursive functions were used, which were invoked repeatedly with the same parameters, I used the Memoize module, which makes caching for functions with the same parameters.

Although the previous function is more efficient for calculating the numberOfOnes just for a single number, it is not when you want to go all the way incrementing to find the next number that satisfies the requested condition. Once we have the numOfOnes for the previous number, we only need to count the numOfOnes that exists in the current number and increment numOfOnes of the previous number.

The following perl on-liner is a better approach to achieve that

The number after the 1 that satisfies the condition countOfOnes(n) = n is

The source code is here.

# NumOfOnes sub num_of_ones{ my $n = shift; return 0 if $n < 1; return 1 if $n <= 9; my @a = split('',$n); my $len = length($n); my $sum = 0; my $delta = 0; if($a[0] > 1){ $delta += 10**($len-1); }else{ $delta += substr($n,1) + 1; } $sum += $delta + $a[0]*num_of_ones(9x($len-1))+ num_of_ones(substr($n,1)); return $sum; }

Since, recursive functions were used, which were invoked repeatedly with the same parameters, I used the Memoize module, which makes caching for functions with the same parameters.

Although the previous function is more efficient for calculating the numberOfOnes just for a single number, it is not when you want to go all the way incrementing to find the next number that satisfies the requested condition. Once we have the numOfOnes for the previous number, we only need to count the numOfOnes that exists in the current number and increment numOfOnes of the previous number.

The following perl on-liner is a better approach to achieve that

perl -e 'while(1){$sum += () = ++$i =~ /1/g; print "Found:$i\n" if $i == $sum;}' Found:1 Found:199981 Found:199982 Found:199983 Found:199984 Found:199985 Found:199986 Found:199987 Found:199988 Found:199989 Found:199990 Found:200000 Found:200001

The number after the 1 that satisfies the condition countOfOnes(n) = n is

**199981**

The source code is here.

## No comments:

Post a Comment