Can any one suggest how to solve these questions in linear time or better than n^2.
1.Given a number N represented in the form of a string S.
Given a number K.
Find how many number less than or equal to N are there whose sum of the digits is divisible by K.
1<=length of the string <=10^5
So O(n^2) does not work here.

2. A good number is one whose sum of the digits is divisible by 5. Given N and K.
   Find the Kth good number greater than N.
   Again O(n^2) solution gives TLE. Any suggestions on optimising.