How to find the count of numbers which are divisib

Question

Given an integer N, how to efficiently find the count of numbers which are divisible by 7 (their reverse should also be divisible by 7) in the range:

• [0, 10^N - 1]

Example:

For N=2, answer:

• 4 {0, 7, 70, 77}

[All numbers from 0 to 99 which are divisible by 7 (also their reverse is divisible)]

My approach, simple brute-force:

• initialize count to zero
• run a loop from i=0 till end
• if a(i) % 7 == 0 && reverse(a(i)) % 7 == 0, then we increase the count

Note:

• reverse(123) = 321, reverse(1200) = 21, for example!

Answer 1

Let COUNTS(n,f,r) be the number of n-digit numbers such that n%7 = f and REVERSE(n)%7 = r

The counts are easy to calculate for n=1:

COUNTS(1,f,r) = 0 when f!=r, since a 1-digit number is the same as its reverse.

COUNTS(1,x,x) = 1 when x >= 3, and

COUNTS(1,x,x) = 2 when x < 3, since 7%3=0, 8%3=1, and 9%3=2

The counts for other lengths can be figured out by calculating what happens when you add each digit from 0 to 9 to the numbers characterized by the previous counts.

At the end, COUNTS(N,0,0) is the answer you are looking for.

In python, for example, it looks like this:

def getModCounts(len):
    counts=[[0]*7 for i in range(0,7)]
    if len<1:
        return counts
    if len<2:
        counts[0][0] = counts[1][1] = counts[2][2] = 2
        counts[3][3] = counts[4][4] = counts[5][5] = counts[6][6] = 1
        return counts
    prevCounts = getModCounts(len-1)
    for f in range(0,7):
        for r in range(0,7):
            c = prevCounts[f][r]
            rplace=(10**(len-1))%7
            for newdigit in range(0,10):
                newf=(f*10 + newdigit)%7
                newr=(r + newdigit*rplace)%7
                counts[newf][newr]+=c
    return counts

def numFwdAndRevDivisible(len):
    return getModCounts(len)[0][0]

#TEST
for i in range(0,20):
    print("{0} -> {1}".format(i, numFwdAndRevDivisible(i)))

See if it gives the answers you're expecting. If not, maybe there's a bug I need to fix:

0 -> 0
1 -> 2
2 -> 4
3 -> 22
4 -> 206
5 -> 2113
6 -> 20728
7 -> 205438
8 -> 2043640
9 -> 20411101
10 -> 204084732
11 -> 2040990205
12 -> 20408959192
13 -> 204085028987
14 -> 2040823461232
15 -> 20408170697950
16 -> 204081640379568
17 -> 2040816769367351
18 -> 20408165293673530
19 -> 204081641308734748

This is a pretty good answer when counting up to N is reasonable -- way better than brute force, which counts up to 10^N.

For very long lengths like N=10^18 (you would probably be asked for a the count mod 1000000007 or something), there is a next-level answer.

Note that there is a linear relationship between the counts for length n and the counts for length n+1, and that this relationship can be represented by a 49x49 matrix. You can exponentiate this matrix to the Nth power using exponentiation by squaring in O(log N) matrix multiplications, and then just multiply by the single digit counts to get the length N counts.

Answer 2

Let's see what happens mod 7 when we add a digit, d, to a prefix, abc.

10 * abc + d =>
  (10 mod 7 * abc mod 7) mod 7 + d mod 7

reversed number:

abc + d * 10^(length(prefix) =>
  abc mod 7 + (d mod 7 * 10^3 mod 7) mod 7

Note is that we only need the count of prefixes of abc mod 7 for each such remainder, not the actual prefixes.

Answer 3

There is a recursive solution using digit dp technique for any digits.

long long call(int pos , int Mod ,int revMod){
    if(pos == len ){
        if(!Mod && !revMod)return 1;
        return 0;
    }
    if(dp[pos][Mod][revMod] != -1 )return dp[pos][Mod][revMod] ;

    long long res =0;
    for(int i= 0; i<= 9; i++ ){
        int revValue =(base[pos]*i + revMod)%7;
        int curValue = (Mod*10 + i)%7;
        res += call(pos+1, curValue,revValue) ;
    }

    return dp[pos][Mod][revMod] = res ;
}