×

# RKABOL04 - Editorial

Author: ravikiran0606
Editorialist: ravikiran0606

EASY-MEDIUM

# PREREQUISITES:

COMBINATORICS, MATH

# PROBLEM:

Given an equation X1 + X2 + ... + XN = K and an array of N numbers a1,a2,...,aN. The task is to find the number of whole number solutions satisfying the given equation such that Xi >= ai for all i (1<=i<=N). Since the no of solutions can be large, print them modulo 109 + 7.

# EXPLANATION:

In this question, we can easily find the case for no solution that if $\displaystyle\sum_{i=1}^{N} X_i$ > K, then no solution exist for that equation. In all other conditions, we can find at least one whole number solution. In order to find the number of whole number solutions for the given equation. Let p = $\displaystyle\sum_{i=1}^{N} X_i$ - K. Now our actual problem reduces to the problem of finding the no of whole number solutions in the new equation, Y1 + Y2 + ... + YN = p without any constraint. The no of solutions to the new equation is similar to the number of ways of distributing p chocolates to N children which can be done in $\binom{p+n-1}{n-1}$ ways.

# AUTHOR'S SOLUTION:

Author's solution can be found here

This question is marked "community wiki".

41
accept rate: 0%

19.6k349497539

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,198
×1,626
×854
×19
×19
×19