We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Lucky Numbers
  5. Discussions

Lucky Numbers

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 69 Discussions, By:

votes

Please Login in order to post a comment

  • vikasandnet
    4 years ago+ 6 comments

    why 23 in between 21 and 25 is not lucky number,

    as we are getting digit sum 5, and sum of square of digits are 13.

    15|
    Permalink
    View more Comments..
  • mateusmuller55
    5 years ago+ 2 comments

    I made this code in C. It works with the sample case, but I fail in all the test cases due to timeout. Why is that?

    #include <stdio.h>
    #include <string.h>
    #include <math.h>
    #include <stdlib.h>
    #include <assert.h>
    #include <inttypes.h>
    int checkPrime(uint64_t s){ /*gets a number and return 1 for prime or 0 otherwise*/
        uint64_t i;
        if (s <= 1)
            return 0;
        if (s == 2)
            return 1;
        if (s % 2 == 0 && s > 2)
            return 0;
        else for (i = 3; i < s/2; i += 2){
            if (s % i == 0)
                return 0;
        }
        return 1;
    }
    int sumSqrDigits(uint64_t a){ /* sum the square of all digits of a number*/
        uint64_t s = 0;
        if (a <= 10)
            return 0;
        while (a  > 0){
            s += (a%10)*(a%10);
            a = a/10;
        }
        return checkPrime(s); /* checks if the sum is a prime number*/
    
    }
    int sumDigits(uint64_t a){ //sum the digits of a number
        uint64_t s = 0;
        if (a <= 10)
            return 0;
        else while (a  > 0){
            s += a%10;
            a = a/10;
        }
        return checkPrime(s); /* checks if the sum is a prime number*/
    }
    int luckyNumbers(uint64_t a, uint64_t b) { /*iterates through all numbers between a and b (included)*/
    
        uint64_t ans = 0, i;
        for (i = a; i <= b; i++){
    
            if ((sumDigits(i) == 1) && (sumSqrDigits(i) == 1)){ // checks if both results are prime
    
            ans++;
            //printf("%"PRIu64"\n", ans);
    
            }
        }
        return ans;
    }
    
    int main() {
        uint64_t a, b, i, cases;
        scanf("%"SCNu64, &cases);
        uint64_t ans[cases];
    
        for(i = 0; i < cases; i++) {
            scanf("%"SCNu64 "%"SCNu64 , &a, &b);
    
            ans[i] = luckyNumbers(a, b);
    
        }
        for (i = 0; i < cases; i++){
            printf("%"PRIu64"\n", ans[i]);
        }
    
        return 0;
    }
    
    4|
    Permalink
  • thoriron2
    3 years ago+ 0 comments
    #include <bits/stdc++.h>
    
    using namespace std;
    
    typedef long long LL;
    
    const int max_num = 1458;
    const int max_sum = 162;
    const int max_length = 19;
    
    LL dp[max_length + 1][max_sum + 1][max_num + 1];
    int digits[max_length + 1];
    bool composite[max_num + 1];
    int len;
    
    void get_primes(){
    
        composite[0] = composite[1] = true;
    
        for(long long i = 2; i * i <= max_num; i++){
            if(!composite[i]){
                for(long long j = i * i; j <= max_num; j+= i){
                    composite[j] = true;
                }
            }
        }
    }
    
    LL rec(int pos, int s1, int s2, int chk)
    {
        if(pos == -1)
            return !composite[s1] && !composite[s2];
    
    
        if(!chk && dp[pos][s1][s2] != -1)
            return dp[pos][s1][s2];
    
        LL ans = 0;
        int end = chk ? digits[pos] : 9;
    
        for(int d = 0 ; d <= end; d++) {
            ans += rec(pos - 1 , s1 + d , s2 + d * d, chk && d == end);
        }
    
        if(!chk)
            dp[pos][s1][s2] = ans;
    
        return ans;
    }
    
    LL get_ans(LL num) {
    
        if(num == 0)
            return 0;
    
        len = 0;
    
        while(num){
    
            digits[len++] = num % 10;
            num /= 10;
        }
    
        LL ans = rec(len - 1, 0, 0, 1);
        return ans;
    }
    
    int main()
    {
        ios::sync_with_stdio(false);cin.tie(0);
    
        int t;
    
        get_primes();
        memset(dp,-1,sizeof(dp));
        cin >> t;
    
        while(t--) {
    
            LL a, b;
            cin >> a >> b;
            cout << get_ans(b) - get_ans(a - 1)  << endl;
        }
    
        return 0;
    }
    
    3|
    Permalink
  • mfbarahonai
    4 years ago+ 0 comments

    If my calculations are right...

    A and B <= 10**18 that means the biggest sum of digits is 999 999 999 999 999 999 (i.e 18 nines). So the biggest number to check as prime is the sum of eighteen squares of nines:

    9*9*18 = 1458
    

    spoiler: 1458 is not prime but 231 numbers below 1458 are prime. Not too many... to store in a list. You can calculate them or copy from here or whatever source you choose:

    primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453]
    

    Checking if number is in the list of primes will save you a for loop check, reducing therefore time complexity of your code.

    Another spoiler: although it is more efficient than a foor loop prime checker, this won't save you to timeout if you loop between A =1 and B =10^18 stepping +1.

    Edit: as stated by @abhiranjan 4 years ago 10^18 instructions may take ~316 years to solve by modern computers. Even them where 32 years or 3 years is unpractical to wait compute that long.

    We need something better.

    3|
    Permalink
  • wilkystorm
    4 years ago+ 0 comments

    13 is a prime number and so is 5 so why isn't 23 considered a "lucky" number 23 5 4,9 13

    2|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature