Cerinta completa

A number is called lucky if the sum of its digits, as well as the sum of the squares of its digits is a prime number. How many numbers between and inclusive, are lucky?

For example, and . Each number is tested below: 

        digit   digit   squares
value   sum     squares sum 
20      2       4,0     4
21      3       4,1     5
22      4       4,4     8
23      5       4,9     13
24      6       4,16    20
25      7       4,25    29

We see that two numbers, , and are lucky.

Note: These lucky numbers are not to be confused with Lucky Numbers

Function Description

Complete the luckyNumbers function in the editor below. It should return an integer that represents the number of lucky numbers in the given range.

luckyNumbers has the following parameter(s):

  • a: an integer, the lower range bound
  • b: an integer, the higher range bound

Input Format

The first line contains the number of test cases .
Each of the next lines contains two space-separated integers, and .

Constraints

Output Format

Output T lines, one for each test case in the order given.

Sample Input

2  
1 20  
120 130

Sample Output

4  
1

Explanation

For the first case, the lucky numbers are , and .
For the second case, the only lucky number is .

Limbajul de programare folosit: java8

Cod:

import java.io.*;
import java.util.*;

public class Solution {
    private static final int MAX_POS = 19;
    private static final int MAX_SUM = 9 * MAX_POS;      // 171
    private static final int MAX_SQ = 81 * MAX_POS;      // 1539

    private static boolean[] primeSum = new boolean[MAX_SUM + 1];
    private static boolean[] primeSq = new boolean[MAX_SQ + 1];

    private static long[][][] memo = new long[MAX_POS + 1][MAX_SUM + 1][MAX_SQ + 1];
    private static int[] digits = new int[MAX_POS];

    private static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;

        FastScanner(InputStream is) {
            this.in = is;
        }

        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }

        long nextLong() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= ' ' && c != -1);

            int sign = 1;
            if (c == '-') {
                sign = -1;
                c = read();
            }

            long val = 0;
            while (c > ' ') {
                val = val * 10 + (c - '0');
                c = read();
            }
            return sign == 1 ? val : -val;
        }

        int nextInt() throws IOException {
            return (int) nextLong();
        }
    }

    private static void sieve(boolean[] prime) {
        Arrays.fill(prime, true);
        if (prime.length > 0) prime[0] = false;
        if (prime.length > 1) prime[1] = false;
        for (int i = 2; i * i < prime.length; i++) {
            if (!prime[i]) continue;
            for (int j = i * i; j < prime.length; j += i) {
                prime[j] = false;
            }
        }
    }

    private static long dfs(int pos, int sum, int sq, boolean tight) {
        if (pos == MAX_POS) {
            return (primeSum[sum] && primeSq[sq]) ? 1L : 0L;
        }

        if (!tight) {
            long v = memo[pos][sum][sq];
            if (v != -1L) return v;
        }

        int limit = tight ? digits[pos] : 9;
        long res = 0;
        for (int d = 0; d <= limit; d++) {
            res += dfs(pos + 1, sum + d, sq + d * d, tight && (d == limit));
        }

        if (!tight) memo[pos][sum][sq] = res;
        return res;
    }

    private static long countLucky(long x) {
        if (x <= 0) return 0;

        for (int i = MAX_POS - 1; i >= 0; i--) {
            digits[i] = (int) (x % 10);
            x /= 10;
        }
        return dfs(0, 0, 0, true);
    }

    public static void main(String[] args) throws Exception {
        sieve(primeSum);
        sieve(primeSq);

        for (int p = 0; p <= MAX_POS; p++) {
            for (int s = 0; s <= MAX_SUM; s++) {
                Arrays.fill(memo[p][s], -1L);
            }
        }

        FastScanner fs = new FastScanner(System.in);
        int t = fs.nextInt();
        StringBuilder out = new StringBuilder();

        for (int i = 0; i < t; i++) {
            long a = fs.nextLong();
            long b = fs.nextLong();
            long ans = countLucky(b) - countLucky(a - 1);
            out.append(ans).append('\n');
        }

        System.out.print(out);
    }
}

Scor obtinut: 1.0

Submission ID: 464614947

Link challenge: https://www.hackerrank.com/challenges/lucky-numbers/problem

Lucky Numbers