Distribute Items

Moderate

0/80

Average time to solve is 31m

Contributed by

4 upvotes

Asked in companies

Problem statement

Find the total number of ways to distribute N items among three people such that :

Each person gets at least one item.

Exactly one person among all the three people gets the maximum number of items.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first and the only line of input will contain an integer N, denoting the total number of items.

Constraints:

0 <= N <= 10^9

Time Limit: 1sec

Output Format:

 The only line of output prints the total number of ways to distribute the items.

Sample Input 1:

Sample Output 1:

Explanation For Sample Input 1:

We can distribute 5 items among three people in total 3 ways i.e. (1, 1, 3) (1, 3, 1) (3, 1, 1) 

NOTE: (1, 2, 2) is not a valid distribution of items since two people have a maximum number of items. Also, (0, 2, 3) is not a valid distribution because 1st person is not having at least one item.

Sample Input 2:

Sample Output 2:

Hint 1

Hint 2

Hint 3

Explore all possible ways one by one iteratively by choosing all possible values for each of 3 persons.

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute Force Approach

As we need to divide N items into 3 parts satisfying the given conditions, each part can have values lying between [1, N - 2] as a minimum each should get at least 1, at max can get (N-2)(when the other two have minimum values i.e 1). So we will explore all possible ways to divide and satisfying the given conditions,

Let ‘count’, be the total number of possible ways to distribute N items (initially 0)
Fixing the first part value (i), using the outer loop, i.e from 1 to N - 2
- Similarly choosing the second value(j) i.e from 1 to N - 2.
- Now we will calculate the third value(k) i.e equals to N - (i + j)
- We will increment our count value by 1 if all three values(i, j, k) satisfy the given conditions i.e (all three i,j,k should be > 0 and one should be strictly greater than the other two).
Return count

Time Complexity

O(N*N), where N is the total number of candies.

Fixing two values by two nested loops(one inside another).

Space Complexity

O(1)

Constant space required

(100% EXP penalty)

Distribute Items

Console