You are given a number N and a number K, count the number of digits <=N which has its sum of digits divisible by K.
eg.N=20,K=4
0,4,8,13,20
O/P-5
1<=N<=10^9
1<=K<=10^9
I encountered this question in a contest. I used the brute force approach(checking for each number less than n whether its sum of digits was divisible by k) but obviously, it did not work for large inputs and gave TLE. So can you suggest an optimized solution that would work for large inputs as well?