UNLUCKY NUMBERS

general
, ,
1

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
2

Why you are asking the same question which is here.

1 Like
3

The problem of checking if a given number is lucky is same as the subset sum problem ryt?

4

@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.

5

@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
6

@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];
7

It Was Still Unanswered There… :slight_smile: Hez expecting a fast reply may be. Try helping him :slight_smile:

Happy coding :slight_smile:

2 Likes
8

@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?

9

@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!

10

@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 .

11

I’m really looking forward to hearing from you! Thank you very much!