Addiction is bad, but I must admit that Interview Street Challenges can be very addictive. This week-end I have started with there latest programming puzzle **Lucky Number**. Very simple puzzle, you are supposed to find sum of the digits of number then find sum of the square of the digits of a number, see if the both the results are prime , If yes then call that number as **Lucky Number**. I have started as usual with brute-force approach, and I knew that they are going to reject my approach right away. Here is the first version of the code, will update this post once I improve some more.

#include <iostream> #include <string> #include <numeric> /* trying with brute force approach */ long long sum_of_digits(long long input) { long long total = 0; while (input != 0) { total += input % 10; input /= 10; } return total; } long long sum_of_square_digits(long long input) { long long total = 0; while (input != 0) { total += (input % 10)* (input % 10); input /= 10; } return total; } bool isPrime(long long x) { long long max = static_cast <long long> (x); if (x <= 0 || x == 1 || (x % 2 == 0 && x != 2)) return false; for (long long i = 3; i < max; i += 2) if (x % i == 0) return false; return true; } int main ( int argc, char** argv) { int T; std::cin >> T; while ( T-- ) { int result = 0; long long A; long long B; std::cin >> A >> B; for ( long long i = A; i <= B; i++) { long long sum = sum_of_digits( i ); long long sum_square = sum_of_square_digits( i ); if ( isPrime(sum) && isPrime(sum_square)){ result++; } } std::cout << result << std::endl; } return 0; }

**Update 2**

Just doing some silly optimization but it also does not accepted by the robot. So this is what I was thinking

1. No need to call square computing function if the sum of the digits are not prime

2. No need compute mod operation twice

3. no need to iterate over the number separately and can be clubed into single function call.

#include <iostream> #include <string> #include <numeric> /* trying with brute force approach */ void sum_of_digits_and_square(long long input, long long& sum, long long& sum_square) { sum = sum_square = 0L; while (input != 0L) { long long digit = input % 10L; sum += digit; sum_square += digit * digit; input /= 10L; } } bool isPrime(long long x) { long long max = static_cast <long long> (x); if (x <= 0 || x == 1 || (x % 2 == 0 && x != 2)) return false; for (long long i = 3; i < max; i += 2) if (x % i == 0) return false; return true; } int main ( int argc, char** argv) { int T; std::cin >> T; while ( T-- ) { int result = 0; long long A; long long B; std::cin >> A >> B; for ( long long i = A; i <= B; i++) { long long sum = 0; long long sum_square = 0; sum_of_digits_and_square(i,sum,sum_square); if ( isPrime(sum)) { if ( isPrime(sum_square)){ result++; } } } std::cout << result << std::endl; } return 0; }

**Attempt No – 2**

#include <iostream> #include <cmath> bool isPrime(long long number) { if (number == 1L) return false; if (number == 2L) return true; if((number & 1) == 0) return false; for (long long d = 3L; d <= (long long)sqrt((double)number); d += 2) if (number % d == 0) return false; return true; } int main ( int argc, char** argv) { int T; std::cin >> T; while ( T-- ) { int result = 0; long long A; long long B; std::cin >> A >> B; for ( register long long i = A; i <= B; ++i) { long long sum = 0; long long sum_square = 0; for (register long long n = i; n > 0; sum += n % 10, n /= 10) ; if ( isPrime(sum)) { for (register long long n = i; n > 0; sum_square += (n % 10) * (n % 10), n /= 10) ; if ( isPrime(sum_square)){ result++; } } } std::cout << result << std::endl; } return 0; }

I’m stuck on this problem as well with no hope in sight. So far I’ve managed to pass 1/9 testcases and I’ve done all the optimizing that I could think of. Have you had any luck with passing all the testcases?

given that max value can be 999999…(18 times ). So max sqaure sum can be 1458. So i have kept one array which keeps primes upto 1458 (there some 236 primes). After that i am doing a binary search.

But still i got TLE.

So the main problem is that given A and B we are iterating over every elements . we need to find a way so that we can skip few elements in between

More and more I think about it , I think we need to apply some thing from number theory.

Only 1/9 test cases passed for me also 😦

I need to optimize my code…any number theory tips?..

ThanQ

Pingback: Longlong max | Janetbosshart