Count numbers with prime digit

Question

Given a number N I need to find the count of the numbers that have atleast one prime digit (2,3,5 or 7) from 1 to N.

Now N can be upto 10^18.What is the best approach to solve this problem.

Example : Let N = 100 the answer is 64.

Please help to solve this problem.

Code : This is main function.But obviously not good approach

    long long int n;
    cin>>n;
    long long int count=0;
    for(int i=1;i<=n;i++){
        long long temp=i;
        while(temp>0){
            int rem=temp%10;
            if(rem==2 || rem==3 ||rem==5 || rem==7){
                count++;
                break;
            }
            temp=temp/10;
        }
    }

Answer 1

quote from comment

the idea is here, but things become a little more complex when you have to remember the allowed digits, I mean for example with N = 645 first digit may be one of {0, 1, 4, 6}, second digit does depend of the value of the first digit... (only {0, 1, 4} for 6 , and also {6, 8, 9} for the first digit in {0, 1, 4})

I think you can think of numbers like 675 as 600 + 70 + 5. Then you calculate separately number of combinations that don't have any prime digit for every component like said in posts above (but we do it only for 0..599, 0..69, 0..5). Then you sum them going from left (600 -> 70 -> 5) as long as first digit of the number is not prime. So you sum resulting numbers of combinations for 600 and 70 because 6 i not prime, but then you don't add combinations for 5 because 7 is prime (that means every number above and equal 670 have prime digit (7 in this case)). This is number of numbers that don't qualify. You have to substract it from original number. You also have to add one because you don't want to count 0.

EDIT I came up with this code

#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
    unsigned long long int number;
    unsigned long long int answer;
    std::cin >> number;
    number += 1; //because we search in range 1..n-1
    std::vector<int> digits;

    unsigned long long int numberCopy = number;
    while(numberCopy)
    {
        int digit = numberCopy % 10;
        digits.push_back(digit);
        numberCopy /= 10;
    }
    std::reverse(digits.begin(), digits.end()); //so digits are in proper order

    int numberOfDigits = digits.size();
    std::vector<unsigned long long int> partialCombinations(numberOfDigits);
    //0, 1,       4,    6,    8, 9
    //0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
    constexpr unsigned long long int nonprimesLessThan[11] = {0, 1, 2, 2, 2, 3, 3, 4, 4, 5, 6};
    constexpr bool prime[10] = {false, false, true, true, false, true, false, true, false, false};

    //we consider each digit as highest digit in number such that all elements in digits array after this digit are equal 0 (so with 3 right most digit = 6 we check for combinations lower than 600)
    unsigned long long int multiplayer = 1; //with numbers like 5999999 on every higher decimal place we have nonprimesLessThan[10] times more combinations 5999999 because we consider numbers that are lower (6000000-1 = 5999999)
    for(int i = numberOfDigits - 1; i >= 0; --i)
    {
        int combinations = nonprimesLessThan[digits[i]] * multiplayer;
        partialCombinations[i] = combinations;
        multiplayer *= nonprimesLessThan[10]; //with numbers like 5999999 on every higher decimal place we have nonprimesLessThan[10] times more combinations
    }
    unsigned long long int sumOfCombinations = partialCombinations[0];
    for(int i = 1; i < numberOfDigits; ++i)
    {
        if(prime[digits[i - 1]]) break;
        sumOfCombinations += partialCombinations[i];
    }
    answer = number - sumOfCombinations;
    std::cout << answer;
    return 0;
}

I can't explain it more than i did in comments. I don't know if it is fully correct either but i can't check it. At least it seems to give good results.

Answer 2

You think this problem needs programming!!

Use mathematics for the answer.

Consider the complementary problem i.e. there is no prime digits in the number. So you can only use digits {0, 1, 4, 6, 8, 9}.

For example How many 2-digits numbers can you make by this set? The answer is 6*6=6^2=36. If N is 100, the answer is 100-36=64.

In a simple case if N is power of 10 then the answer is N - 6^log(N).

Now how about N is not power of 10. Consider N=57. In this case when the first digits is lower than 5. You can use {0, 1, 4} for the first digit and {0, 1, 4, 6, 8, 9} for the second one. Therefor answer is 57-3*6+1=40. (Zeros is excluded in the main question, so the answer is increamented).

Answer 3

This kind of problems can be solved with pretty standard dynamic programming:

1)Let's construct the number starting from the most significant to the least significant digit. The state is: (len, was, greater), where len is the number of digits already processed, was is a boolean value which indicates whether 2, 3, 5 or 7 was already added and greater is boolean value which is true if N is greater than current prefix and false if it is equal to it(note that if the current prefix is greater than N then it is invalid). The value of each state is the number of ways to construct such prefix.

2)Base case: f(0, 0, 0) = 1. There is only one way to construct an empty prefix. To compute other values, one can iterate over len and try to add each valid digit.

Here is my C++ code:

long long compute(string N) {
    static set<int> good({2, 3, 5, 7});
    int len = N.length();
    vector<vector<vector<long long>>> f(len + 1, 
        vector<vector<long long>>(2, vector<long long>(2)));
    f[0][0][0] = 1; //base case
    for (int i = 1; i <= len; i++)
        for (int was = 0; was <= 1; was++)
            for (int gt = 0; gt <= 1; gt++) 
                for (int d = 0; d <= 9; d++) {
                    bool n_was = was || good.count(d);
                    bool n_gt = false;
                    if (gt) {
                        n_gt = true;
                    } 
                    else {
                        if (N[i - 1] - '0' < d) //Invalid prefix
                            continue;
                        if (N[i - 1] - '0' > d)
                            n_gt = true;
                    }
                    f[i][n_was][n_gt] += f[i - 1][was][gt];
                }
    return f[len][1][0] + f[len][1][1];
}

3)The time complexity is O(length(N)) which is O(log N).