## PayPal Interview Question

abcs**Country:**India

**Interview Type:**In-Person

using a program to solve this,

Note: it also prints out the combination

```
public class Com1ToN
{
static int count;
public static void main(String[] args)
{
count = 0;
System.out.print("Enter N : ");
int n = (new Scanner(System.in)).nextInt();
for (int i = 0; i < n; i++)
print(1, n, i, "");
System.out.println("The count is : " + count);
}
private static void print(int s, int n, int lvl, String pre)
{
if (lvl == 0)
for (int i = s; i <= n; i++) {
System.out.println(pre + i);
count++;
}
else
for (int i = s; i <= n - lvl; i++)
print(i + 1, n, lvl - 1, pre + i + " ");
}
}
```

If we assume that every pearl is unique in their magnificence we can say that adding the nth pearl to our set will let us create all the necklaces that does not have it f(n-1) + all those combinations with the new pearl + one necklace that is just the new pearl. Thus we get f(n) = 2*f(n-1) + 1. And f(1) = 1.

If we assume that there are multiple pearls with the same magnificence value but are otherwise identical then we can break the problem down into progressively adding pearls of a new level of magnificence. If there are x[i] pearls of i magnificence then we can add between 0 and x[i] pearls to all the necklaces we had when only considering the necklaces with inferior quality. And all the new necklaces with just the pearls of magnificence i . So we get f(i) = f(i-1) * (x[i] + 1) + x[i]. where f(0) = x[0]

If all the pearls are unique but some have the same level of magnificence then we need to consider all the ways we can add each set of pearls of the same magnificence. Each sub necklace consists of from 1 to x[i] pearls and each of these can have m! was to be arranged where m is the length of the necklace. For this we get SUM(m = 1 to x[i], m!)

f(i) = f(i-1) * (SUM(m = 1 to x[i], m!)+ 1) + SUM(m = 1 to x[i], m!). where f(0) = SUM(m = 1 to x[0], m!)

This is a bit too mathematical...

- PeyarTheriyaa August 22, 2018choosing 1 from n is nC1

choosing 2 from n is nC2

choosing 3 from n is nC3... till

choosing n from n is nCn

each combination should be added to get the total no of possible formations

nC1+nC2+...+nCn

(without going into the derivation its known that) nC0+nC1+...+nCn=2^n

nC0=1

therefore

nC1+nC2+...+nCn=(2^n)-nC0

so, nC1+nC2+...+nCn=(2^n)-1