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$
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)? 🤔
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:
I took this chance to further mess around with BigInt in zig and ended up with this:
conststd=@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 - 19constBigInt=std.math.big.int.Managed;pubfnsevens(alloc:std.mem.Allocator,digits:u32)!BigInt{if(digits==1){returntryBigInt.initSet(alloc,1);}else{// result = 10 * last + 10^(n-1) - last// = 9 * last - 10^(n-1)varresult=tryBigInt.initSet(alloc,9);varlast=trysevens(alloc,digits-1);deferlast.deinit();varadditional=tryBigInt.initSet(alloc,10);deferadditional.deinit();tryresult.mul(&result,&last);tryadditional.pow(&additional,digits-1);tryresult.add(&result,&additional);returnresult;}}pubfnmain()!void{conststdout=std.io.getStdOut().writer();vargpa=std.heap.GeneralPurposeAllocator(.{}){};constalloc=gpa.allocator();inlinefor(1..30)|i|{constdigits=@intCast(u32,i);varnumber=tryBigInt.initSet(alloc,10);defernumber.deinit();trynumber.pow(&number,digits);varresult=trysevens(alloc,digits);deferresult.deinit();trystdout.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.
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)
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);
}
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.
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.
We're a place where coders share, stay up-to-date and grow their careers.
Using Rust:
We iterate until 19 digits, we will get an overflow for
i64.Output:
Explanation for the math behind the current solution can be found here: flyingcoloursmaths.co.uk/percentag...
Can't you simply directly compute the percentage? I.e.
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$
By the way, you can write LaTeX on Dev using
{% katex %} {% endkatex %}(You need to double-escape#'s though)You are right, it can be simplified as you pointed out. Thank you :)
Generalized for any number:
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)? 🤔Done!
GitHub file
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:
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:
I took this chance to further mess around with BigInt in zig and ended up with this:
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:
* Since every range of
nnumbers has at least the range7*(n-1) to 8*(n-1)-1, which is exactlyn-1numbers 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.Except the first one is 10% not 1%
Yes, without that 10%, turning the number into a percentage would have been a really simple string operation, but since
1is 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)
Due to the limitations of stack size, my true genius is limited to 10000, but I'm sure you get the idea.
Using Java :D
Output:
Another Rust solution:
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.
My take using F#.
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.