Number of ways to divide n objects in k groups, such that no group will have fewer objects than previously formed groups?

,
1

Number of ways to divide n objects in k groups, such that no group will have fewer objects than previously formed groups?

eg.
n=7
k=3

number of ways=4

explaination:

1 1 5

1 2 4

1 3 3

2 2 3

2 Likes
2

Can anyone please help me to solve this problem?

3

Hi!
There are multiple solutions to this problem but I will discuss two of them.

  1. You can use DP to solve this problem, where your DP states will be the number of objects, position, and number of objects in the last group.
    That is, dp[pos][n][last] (while filling the DP table, place the value accordingly so that they are in increasing order in count)

  2. Here you can optimize the above DP states to dp[n][k](distributing n objects to k groups), then
    for n> =k: you can either distribute 1 to all of the k groups and again call dp[n-k][k]
    OR you can place 0 object in 1 group and call dp[n][k-1] .
    Otherwise, the same idea can be applied to last n groups out of k groups as n is less than ‘k’ here.

I hope i made it clear to you.

5 Likes
4

Wow. nice approach :ok_hand:t2:

5

This is from hackerearth circuits right…

6

Nope…
This is from some companies hiring challenge on Hackerrank. This challenge already finished on 28-08-2019

7

Got it… Sorry buddy , actually something similar type question so, …
Ps which company for u give this xam

8

This question has also come in the Expedia intern hiring test today.

9
10

This was in yesterday 's linked in sde intern test too :cry: unfortunately i was not able to solve this problem

1 Like