Hi everyone,
I’m struggling with this problem, and I don’t have any idea to do it yet. Does anyone know how to solve it?
A positive integer is called a lucky number when the sum of some of its digits equals the sum of its remaining digits. 561743, for example, is a lucky number because 5 + 1 + 4 + 3 = 6 + 7. However, we are about to count the number of unlucky numbers with the length of N and their digits are in the range [0, K], and they could start with a bunch of ‘0’.
Input: N K Output: The number of unlucky numbers
Example 1:
Input
1 5
Output
5
Example 2:
Input
4 3
Output
164
1 Like
Why you are asking the same question which is here.
1 Like
The problem of checking if a given number is lucky is same as the subset sum problem ryt?
@voanhkhach : You have not specified the constraints on N and K . The correct/best approach would depend on that . i.e. i want to know if N can get very large k being less than 10 or 20 . or k can go large , n being 10 or 20 , or both n and k can be large . And large then how big they can be.
@voanhkhach : You can solve the problem with Dynamic programming .
Make the function f[i][j] as :
Number of i digit numbers whose digits can be partitioned into two parts such that difference of sum of digits in each partition is j .
Then ,
f[i][j] = sum( p = 0 to k) f[i][j+p]
Initial conditions :
f[1][i] = 1 , for all 0 <= i <= k .
The time complexity of the algorithm will be O ( k * n * n)
You will need to allocate a two dimensional array f[][] .
f[1] will have length k + 1 .
f[2] will have length 2 * (k+1) .
f[3] will have length 3 * (k+1) . and so on
1 Like
@vineetpaliwal:
Could you please explain this formula?
f[i][j] = sum( p = 0 to k) f[i][j+p]
This is my code, and I don’t think F[i][j] will be modified with that formula.
for (i = 1; i <= N; ++i)
for (j = 0; j <= i * K; ++j)
for (p = 0; p <= K; ++p)
F[i][j] = F[i][j] + F[i][j+p];
It Was Still Unanswered There… Hez expecting a fast reply may be. Try helping him
Happy coding
2 Likes
@vineetpaliwal: Thank you a lot for your reply!
These are the constraints on N and K:
1 <= N <= 20
1 <= K <= 9
And I don’t think K could be larger than 9 because it is about the digits. Could you please explain in details to me how you approach this problem?
@vineetpaliwal: I know you’re busy, but could you spare a little of time to help me out with this problem?
Thank you very much!
@voanhkhach : Sorry i forgot about this thread . Its early morning in India and I am getting ready for office . I will reply later in the day .
I’m really looking forward to hearing from you! Thank you very much!