[Community Puzzle] The Lucky Number

Struggled through this puzzle and discovered in a hard way that the Math library in Java will sometimes produce a precision error when producing long integer results.

long n = (long)Math.pow(9, 17)

n value given by java is 16677181699666570
using a calculator to cross check, 9^17 is 16677181699666569

Math.pow deals with double. It loses precision when double is cast to long. I believe many other languages have a similar limitation, causing strange errors when solving extreme problems.

It’s not anything to do with the casting to long, the precision is lost as soon as you use the double type. The IEEE standard for a double precision float (https://en.wikipedia.org/wiki/Double-precision_floating-point_format) cannot actually represent that value as it only has 53 bits of precision (9^17 requires 54 bits to represent exactly).

Doing the calculation of 9^17 manually inside a long variable will work correctly as it never gets converted into a double.


I wrote some logic in java to solve this problem but I am unable to run last 2 test cases because of time limit.

In 2 Seconds,to run these 2 test cases it is some what difficult for me.
Test Cases: 64-bit Number (92871036442 3363728910382456)
Biggest Number(1 1000000000000000000)

Did anyone solve this problem?
Please let me know. It will be helpful.


I passed all the tests in the IDE but my code doesn’t pass the 4th and 5th validators.

EDIT: I found the problem. Please can someone add the following tests in the IDE:
input: 5999 6000
output: 1

input: 7148 8875
output: 1018

These two inputs did not give me the good results with my old code.

A bit late, but I would also like to know how to go about passing these two test cases.
My current solution consists of going through all possible numbers, then counting each digit in that number.

I’ve figured out how to pass the 5th test in the IDE (64-bit integer) but somehow it does not pass for the last test (Biggest). My code is missing only 2 lucky numbers, and I cannot figure out where I’m missing something. Has anybody had a similar issue?

What language do you use ?

I’m using C++.

Maybe try with unsigned long long but I see that most C++ solutions just use long long and work fine so it’s probably not the problem.

I tried it in case but it did not change the behavior.

Hi all , i’m a newbie at prolog, i’m trying to resolve this exercise Coding Games and Programming Challenges to Code Better

I’m not able to resolve it, what i got so far is this

At first step i was trying to check a list of single digit (1,10) it seems to count 6 and 8 (if i debug the code i see that the var P goes to 2) but then the output is 0 :\

Also i don’t know how to edit the check in order to works with more digits (like 16) as well, if someone could explain it to me would be really appreciate.

  1. I knew Prolog some years ago but now I know I have forgotten all its syntax.
  2. CG is not supporting Prolog yet, I believe.
  3. Your approach is similar to using a regular expression to test each number in the range. This is brute force approach. It should work for small ranges (if coded correctly). It is very likely to time out when the range comes to a million or more.
  4. No harm using this puzzle to learn Prolog offline. Even better you could find some logical puzzles to try out Prolog, to fully utilize this tool’s potential.

EDIT: i made several changes (i would prefer to just spam the link to source code, but it doesn’t let me post the link :\ )

/* A lucky number is a 10-based number, which has at least a "6" or an "8" in its digits. 
 * However, if it has "6" and "8" at the same time, then the number is NOT lucky. 
 * For example, "16", "38", "666" are lucky numbers, while "234" , "687" are not.
 * Now we want to know how many lucky numbers (without leading zeroes)
 * are there between L and R, inclusive?
 * L is LowerBound
 * R is UpperBound
 * P is the total occurence of lucky numbers
 * between_to_list -> generates all the numbers between L and R included
 * digits -> convert the number in digits
 * check_number -> check if Cs (number converted in digits) contains 6 and
 * 				 not contain 8, or contains 8 and not contain 6, if these constraints
 * 				 are satisfied increment P by 1
 * query tested -> generate_interval(6,16)
 * I generate all numbers and then i move backward from R to L and i check every number,
 * 16 is the first element checked, indeed P is incremented to 1, then the program check
 * 15 and it fails, after the fail the program quit*/


between_to_list(X,X,0) :- !.
between_to_list(X,Y,P) :-
    X =< Y,
    Z is X+1,

digits(X,Cs):-number_chars(X, Cs).

    memberchk('6', Cs),
    not(memberchk('8', Cs)),
    P is P1+1;
    memberchk('8', Cs),
    not(memberchk('6', Cs)),
    P is P1+1.

now i’m able to work with N digits, and the counter should be implemented in the right way as well, the problem is that i don’t know how to keep program iterate after the 1st fail on the check. I assume that if this problem is solved then all should works properly.
If someone could give me a feedback would be really appreciate.

Hello, I’ve done a program to count numbers with “6”; “8”; and both, it looks good, I’ve tried it in my own IDE, counting manually and with my CG program, with good results in the test cases, but the test “larger” doesn’t give me the correct answer but “312524”, even when I count “manually”. Lucky numbers are numbers with “6” or “8” in their digits, and not both of them right ? Thanks for your help !

Count “manually”? I would not believe I can do it correctly when the range is hundreds of thousands of numbers.

Wanted numbers have at least a “6” or an “8” but not both. The difficulty is in counting it fast enough.

Here is my testing program, in my own IDE, to check if my code is right. It is. But in the test case “larger”, it doesn’t give me the good answer, and it’s not because of time. So, I wonder if there is not a piece of the statement that I missed.

v = True
i = 361087
c = 0
for j in range(i+1) :
    if str(j).count("6") == str(j).count("8") :
        c += 1
if c != my_program(i) :
    v = False
print(v, c, my_program(i))

You missed this:

A lucky number is a 10-based number, which has at least a “6” or an “8” in its digits. However, if it has “6” and “8” at the same time, then the number is NOT lucky.

Thanks, I will try this
I have done a logical error :’(

Update : It’s done, it works, thanks

1 Like