PROBLEM LINK:
Author: Kaushambi Gujral
Tester: Shivani Srivastava
Editorialist: Kaushmabi Gunjral
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Number Theory
PROBLEM:
We are provided with ‘N’ type of beads, and we need to compute the maximum number of necklaces that can be formed by the given number of beads. To make a good necklace we must include atleast one bead.
QUICK EXPLANATION:
We need to compute (2 ^ N) -1.(N is the number of beads)
EXPLANATION:
The first point to be noticed should be, that ATLEAST one bead has to be there in the necklace if N>=1. Of course, that if N=0, no necklace is possible and the answer is 0.
Let us consider the case of N=3. Here, if I represent the type of beads by ‘a’, ‘b’ and ‘c’ respectively, then the possible combinations could be:
• 1 necklace with all the three beads. abc (3C3 way)
• 3 necklaces with 2 types of beads each. ab, bc, ca (3C2 ways)
• 3 necklaces with only 1 bead each. a, b, c (3C1 ways)
TOTAL= 1+3+3 = 7
So, we are looking for COMBINATIONS. One direct thing that comes to our minds is, that we have to calculate the following-
NCN + NC (N-1) +NC (N-2) +…+NC1
This is the brute-force approach and most of us get stuck with a T.L.E. One more thing to be taken care of is that we are asked to print the total SUM and not the value of each combination. So there has to be an easy way out!
If we take many cases and try to solve them on sheet of paper, we will realise that there is a direct way to calculate this SUM. Try this out: (2^N)-1
If N=3, the answer would be (2^3)-1 = 7. (Correct!) The problem, thus, gets reduced to calculating 2^N and subtracting 1 from the same.
For those who got confused with mod(10^5): While calculating 2^N, modulo the result by 10^5.
AUTHOR’S AND TESTER’S SOLUTIONS:
The solution can be found here