Challenge: Counting Numbers with 7s

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 calculate the percentages for the following ranges:

• 0-99
• 0-999
• 0-9999
• 0-99999
• etc.

The program should take a single integer input n that represents the maximum range (exclusive), i.e., the program will calculate the percentage of numbers containing a 7 in the range from 0 to n-1.

You may use any programming language of your choice. Extra imaginary bonus points for a performant approach that can handle larger and larger ranges efficiently.

Examples

Input => Output

10 => 10.00%
100 => 19.00%

In the first example, 1/10 numbers (10%) contain a 7 (just the number 7).

In the second example, 19/100 numbers (19%) contain a 7 (10 numbers from 70 to 79, plus 7, 17, 27, 37, 47, 57, 67, 77, 87, 97). Thus, the output is "19.00%".

Have fun!

7️⃣ 7️⃣ 7️⃣

Cover image via Unsplash.

Comments

[Ervin Szilagyi]

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);
    }
}

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%

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

[lionel-rowe]

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
}

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)? 🤔

[MoshiKoi]

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

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

let percent = f64::powf(0.9, i as f64) * 100.0

[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$

[MoshiKoi]

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

$$percentage=\frac{\#noseven}{\#total}=9^n/10^n=0.9^n$$

[Ervin Szilagyi]

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

[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)}%")

GitHub file

[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) ;

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

[𒎏Wii 🏳️‍⚧️]

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 });
    }
}

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

---

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

[Matt Ellen]

Except the first one is 10% not 1%

[𒎏Wii 🏳️‍⚧️]

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)

[Matt Ellen]

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

})();

[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);
}

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%

[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%

[MoshiKoi]

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));
    }
}

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.

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