Count the number of 1's

I've participated in a Quiz where i had to implement a function that counts the number of 1's required to reach a positive integer passed as a parameter.

Example:

view plainprint?

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

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 ).

At first glance I've implemented a perl one-liner that returns the number of 1's for an input number. Here it is:

view plainprint?

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

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

view plainprint?

1. NumberOfOnes=36  

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:

view plainprint?

1. # NumOfOnes  
2. sub num_of_ones{  
3.   my $n = shift;  
4.   
5.   return 0 if $n < 1;  
6.   return 1 if $n <= 9;  
7.   
8.   my @a = split('',$n);  
9.   
10.   my $len = length($n);  
11.   my $sum = 0;  
12.   my $delta = 0;  
13.   
14.   if($a[0] > 1){  
15.     $delta += 10**($len-1);  
16.   }else{  
17.     $delta += substr($n,1) + 1;  
18.   }  
19.   
20.    $sum += $delta + $a[0]*num_of_ones(9x($len-1))+ num_of_ones(substr($n,1));  
21.    return $sum;  
22. }  

# 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

view plainprint?

1. perl -e 'while(1){$sum += () = ++$i =~ /1/g; print "Found:$i\n"  if $i == $sum;}'  
2.   
3. Found:1  
4. Found:199981  
5. Found:199982  
6. Found:199983  
7. Found:199984  
8. Found:199985  
9. Found:199986  
10. Found:199987  
11. Found:199988  
12. Found:199989  
13. Found:199990  
14. Found:200000  
15. Found:200001  

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.