DEV Community

Cover image for Challenge: Counting Numbers with 7s

Challenge: Counting Numbers with 7s

Peter Kim Frank on April 18, 2023

Prompt Write a program to calculate the percentage of numbers in a given range that contain the digit 7. Your program should be able to ...
Read full post
Collapse
 
ervin_szilagyi profile image
Ervin Szilagyi • • Edited

Using Rust:

fn main() {
    for i in 1..19 {
        let n = i64::pow(10, i) as f64;
        let contains_sevens = n - f64::powf(0.9, i as f64) * n;
        let percent = contains_sevens * 100.0 / n;
        println!("{}-{:.2}%", n, percent);
    }
}
Enter fullscreen mode Exit fullscreen mode

We iterate until 19 digits, we will get an overflow for i64.

Output:

10-10.00%
100-19.00%
1000-27.10%
10000-34.39%
100000-40.95%
1000000-46.86%
10000000-52.17%
100000000-56.95%
1000000000-61.26%
10000000000-65.13%
100000000000-68.62%
1000000000000-71.76%
10000000000000-74.58%
100000000000000-77.12%
1000000000000000-79.41%
10000000000000000-81.47%
100000000000000000-83.32%
1000000000000000000-84.99%
Enter fullscreen mode Exit fullscreen mode

Explanation for the math behind the current solution can be found here: flyingcoloursmaths.co.uk/percentag...

Collapse
 
lionelrowe profile image
lionel-rowe • • Edited

Generalized for any number:

fn sevens(n: f64) -> f64 {
    let i = f64::log10(n);

    let contains_sevens = n - f64::powf(0.9, i as f64) * n;
    let percent = contains_sevens * 100.0 / n;

    percent
}
Enter fullscreen mode Exit fullscreen mode

Then it only returns an approximation for numbers that aren't powers of ten, though.

Without going the brute-force route (checking every number from 0..n), is there some way of getting a more accurate estimate, or even an exact answer (well, as exact as you can get with floating point)? 🤔

Collapse
 
moshikoi profile image
MoshiKoi • 
let contains_sevens = n - f64::powf(0.9, i as f64) * n;
let percent = contains_sevens * 100.0 / n;
Enter fullscreen mode Exit fullscreen mode

Can't you simply directly compute the percentage? I.e.

let percent = f64::powf(0.9, i as f64) * 100.0
Enter fullscreen mode Exit fullscreen mode
Collapse
 
peteole profile image
Ole Petersen •

Think so too, since a number contains no seven iff all of its digits contain no seven, so the amount of numbers without sevens is the amount of numbers with the remaining nine digits:
$percentage=\frac{#noseven}{#total}=9^n/10^n=0.9^n$

Thread Thread
 
moshikoi profile image
MoshiKoi •

By the way, you can write LaTeX on Dev using {% katex %} {% endkatex %} (You need to double-escape #'s though)

percentage=#noseven#total=9n/10n=0.9n percentage=\frac{\#noseven}{\#total}=9^n/10^n=0.9^n
Collapse
 
ervin_szilagyi profile image
Ervin Szilagyi •

You are right, it can be simplified as you pointed out. Thank you :)

Collapse
 
maxwellnewage profile image
Maximiliano Burgos •

Done!

def percentage_of_7(given_range: int):
    seven_amount = 0
    numbers = list(range(given_range))

    for n in numbers:
        if '7' in str(n):
            seven_amount += 1

    per_of_7 = (seven_amount * 100) / len(numbers)

    return per_of_7


print(f"{percentage_of_7(10)}%")
Enter fullscreen mode Exit fullscreen mode

GitHub file

Collapse
 
rjwhite profile image
RJ White •

Using Perl

My example is not as elegant as the Rust example from @ervin, as mine is a simple brute force version and has no intelligence of the math involved - and I felt that using the link he provided that showed a smart algorithm would be nothing more than really using a Perl version of his work. So points should go to him.

I include this only as an example of Perl in case anyone were interested. For brevity there is almost no error handling and no comments. It is memory efficient but not CPU efficient. Once you get up to around ten million, it becomes very inefficient:

#!/usr/bin/env perl

my $num = $ARGV[0] or die "you need to provide a number!\n" ;

my $range = 10 ;
while ( $range <= $num ) { 
    my $sevens_cnt = 0 ;
    for ( my $i=1 ; $i <= $range ; $i++ ) {
        $sevens_cnt += 1 if ( $i =~ /7/ ) ;
    }
    my $percentage = $sevens_cnt * 100 / $range ;
    printf( "%-08d => %0.2f%%\n", $range, $percentage ) ;
    $range *= 10 ;
}
exit(0) ;
Enter fullscreen mode Exit fullscreen mode

and the output, showing the time taken for ten million is a little over 2 seconds on my 10 year old T420 Thinkpad. Anything higher and it will start to be real slow:


laptop7> time ./counting-sevens.plx  10000000
10       => 10.00%
100      => 19.00%
1000     => 27.10%
10000    => 34.39%
100000   => 40.95%
1000000  => 46.86%
10000000 => 52.17%
2.336u 0.000s 0:02.33 100.0%    0+0k 0+0io 0pf+0w
Enter fullscreen mode Exit fullscreen mode
Collapse
 
darkwiiplayer profile image
𒎏Wii 🏳️‍⚧️ • • Edited

I took this chance to further mess around with BigInt in zig and ended up with this:

const std = @import("std");

// Starting from scratch (again)
// 1 to 10 = 1
// 1 to 100 = 10 times 1 + 10 - 1 => 19
// 1 to 1000 = 10 times 19 + 100 - 19

const BigInt = std.math.big.int.Managed;

pub fn sevens(alloc: std.mem.Allocator, digits: u32) !BigInt {
    if (digits == 1) {
        return try BigInt.initSet(alloc, 1);
    } else {
        // result = 10 * last + 10^(n-1) - last
        //        = 9 * last - 10^(n-1)
        var result = try BigInt.initSet(alloc, 9);
        var last = try sevens(alloc, digits - 1);
        defer last.deinit();
        var additional = try BigInt.initSet(alloc, 10);
        defer additional.deinit();
        try result.mul(&result, &last);
        try additional.pow(&additional, digits - 1);
        try result.add(&result, &additional);
        return result;
    }
}

pub fn main() !void {
    const stdout = std.io.getStdOut().writer();

    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    const alloc = gpa.allocator();

    inline for (1..30) |i| {
        const digits = @intCast(u32, i);

        var number = try BigInt.initSet(alloc, 10);
        defer number.deinit();
        try number.pow(&number, digits);

        var result = try sevens(alloc, digits);
        defer result.deinit();

        try stdout.print("For 0-{s}: {}\n", .{ "9" ** i, result });
    }
}
Enter fullscreen mode Exit fullscreen mode

I couldn't be bothered to figure out calculating a percentage, but that's just adding a . after the second digit and a % sign at the end, so who cares.*

Here's my results:

For 0-9: 1
For 0-99: 19
For 0-999: 271
For 0-9999: 3439
For 0-99999: 40951
For 0-999999: 468559
For 0-9999999: 5217031
For 0-99999999: 56953279
For 0-999999999: 612579511
For 0-9999999999: 6513215599
For 0-99999999999: 68618940391
For 0-999999999999: 717570463519
For 0-9999999999999: 7458134171671
For 0-99999999999999: 77123207545039
For 0-999999999999999: 794108867905351
For 0-9999999999999999: 8146979811148159
For 0-99999999999999999: 83322818300333431
For 0-999999999999999999: 849905364703000879
For 0-9999999999999999999: 8649148282327007911
For 0-99999999999999999999: 87842334540943071199
For 0-999999999999999999999: 890581010868487640791
For 0-9999999999999999999999: 9015229097816388767119
For 0-99999999999999999999999: 91137061880347498904071
For 0-999999999999999999999999: 920233556923127490136639
For 0-9999999999999999999999999: 9282102012308147411229751
For 0-99999999999999999999999999: 93538918110773326701067759
For 0-999999999999999999999999999: 941850262996959940309609831
For 0-9999999999999999999999999999: 9476652366972639462786488479
For 0-99999999999999999999999999999: 95289871302753755165078396311
Enter fullscreen mode Exit fullscreen mode

* Since every range of n numbers has at least the range 7*(n-1) to 8*(n-1)-1, which is exactly n-1 numbers long, for every input range there will be at least 10% sevens, and for obvious reasons there can't be 100%, so we always end up with a two-digit percentage. Since the range is always a power of 10 in length, the percentage is just the number of sevens with a decimal point added.

Collapse
 
mellen profile image
Matt Ellen-Tsivintzeli •

Except the first one is 10% not 1%

Collapse
 
darkwiiplayer profile image
𒎏Wii 🏳️‍⚧️ • • Edited

Yes, without that 10%, turning the number into a percentage would have been a really simple string operation, but since 1 is single digit, you can't add a dot after the second digit without, well, first adding a second digit (a zero, of course) so that would require a bunch of extra logic that I didn't want to bother with.

(also ngl I haven't used strings in zig enough to know how to do that, and didn't want to look it all up when I already had to look up so much of the bigint stuff)

Collapse
 
mellen profile image
Matt Ellen-Tsivintzeli • • Edited

Due to the limitations of stack size, my true genius is limited to 10000, but I'm sure you get the idea.

(function()
{
    function bigAbs(x) 
  {
    return x < 0n ? -x : x
  }

  const hasASevenList = [7n];

  function hasASeven(n)
  {
    if(hasASevenList.includes(n))
    {
      return true;
    }

    const lastDigit = n % 10n;

    const has7 = lastDigit == 7n;

    if(has7)
    {
      hasASevenList.push(n);
      return true;
    }
    else
    {
      if(n < 7n)
      {
        return false;
      }
      else
      {
        return hasASeven(n/10n);
      }
    }

  }

  //assume n is a BigInt, because otherwise we'd have to go home.
  function howManySevens(count, end)
  {
    end = bigAbs(end); //negative numbers gtfo

    end = end -1n;

    if(end < 7n)
    {
      return count;
    }
    else
    {
      const has7 = hasASeven(end);
      if(has7)
      {
        return howManySevens(count+1n, end);
      }
      else
      {
        return howManySevens(count, end);
      }
    }
  }

  return howManySevens(0n, 1000n)*100n/1000n

})();
Enter fullscreen mode Exit fullscreen mode
Collapse
 
fmarcos8 profile image
Francisco M. Marcos •

Using Java :D

final int MAX = 8;
for (int i = 1; i <= MAX; i++) {
       int count_sevens = 0;
       var n = Math.pow(10, i);
       for (int j = 0; j <= n; j++) {
            if (String.valueOf(j).contains("7")) {
                count_sevens++;
            }
       }
      float percent = (float) (count_sevens * 100 / n);
      System.out.printf("%.0f => %.1f%%\n", n, percent);
}
Enter fullscreen mode Exit fullscreen mode

Output:

10 => 10,0%
100 => 19,0%
1000 => 27,1%
10000 => 34,4%
100000 => 41,0%
1000000 => 46,9%
10000000 => 52,2%
100000000 => 14,0%
Enter fullscreen mode Exit fullscreen mode
Collapse
 
nekroido profile image
Artem Smirnov •

My take using F#.

let contains digit =
    string >> String.exists (string >> (=) (string digit))

let percentOf f numbers =
    let total = numbers |> Seq.length |> float
    let matched = numbers |> Seq.filter f |> Seq.length |> float

    matched / total * 100.

let calculatePercent upper digit =
    printf
      "%d => %g%%\n"
      upper
      (seq { 0L .. upper } |> percentOf (contains digit))

calculatePercent 9 7   // 9 => 10%
calculatePercent 99 7  // 99 => 19%
calculatePercent 999 7 // 999 => 27.1%
Enter fullscreen mode Exit fullscreen mode
Collapse
 
moshikoi profile image
MoshiKoi • • Edited

Another Rust solution:

fn sevens(n: i64) -> i64 {
    match n {
        7..=16 => { return 1; },
        0..=6 => { return 0; },
        _ => {}
    };

    let deg = 10_i64.pow(n.ilog(10));
    let (lead, rest) = (n / deg, n % deg);

    let base = lead * sevens(deg - 1);

    match lead {
        8..=9 => base + deg,
        7 => base + rest,
        1..=6 => base,
        _ => unreachable!()
    }
}

fn percent_sevens(n: i64) -> f64 {
    sevens(n) as f64 / n as f64
}

fn main() {
    for i in 1..19 {
        let limit = 10_i64.pow(i);
        println!("{} {:.2}%", limit, percent_sevens(limit));
    }
}
Enter fullscreen mode Exit fullscreen mode

Uses a fairly simple recursive approach that could probably be optimized. It uses the fact that the numbers 1xxx, 2xxx, 3xxx all contain the same number of 7s in them, so we can just multiply by the leading digit to get the answer.

Collapse
 
itsahsanmangal profile image
Ahsan Mangal 👨🏻‍💻 •

This article provides an engaging and thought-provoking exercise for developers looking to hone their problem-solving and algorithmic skills. The problem is well-defined and encourages readers to think creatively to find an efficient solution.