-2
\$\begingroup\$

Problem Statement

Shil, Aditya and Utkarsh go to a candy shop. There are N candies present in the shop, which are indexed from 1 to N. All three of them select one candy to eat.

However, a candy tastes delicious if and only if, the index of candy chosen by Shil is strictly less than the index of candy chosen by Aditya and the index of candy chosen by Aditya is strictly greater than index of candy chosen by Utkarsh.

To state in simple Mathematical terms, if Shil chooses ith candy, Aditya chooses jth candy and Utkarsh chooses kth candy, then the candies would taste delicious

if and only if i < j and j > k.

You have to find the total number of ways in which they can choose candies such that the candies would taste delicious to them. Note that all of them choose distinct number of candies i.e., i!=j and j!=k and i!=k.

Input format:

The only line of input consists of a single integer N denoting the total number of candies.

Output format:

Find the total number of ways by which all three can choose candies such that the candies would taste delicious to them.

Constraints:

\$3 \le N \le 1000\$

Sample Input

4

Sample Output

8

Explanation:
All the possible ways to choose candies are:

[1,3,2]
[2,3,1]
[2,4,3]
[3,4,2]
[1,4,3]
[3,4,1]
[2,4,1]
[1,4,2]

The first integer in all the tuples denotes index of candy chosen by Shil, the second integer denotes index of candy chosen by Aditya and the third integer denotes index of candy chosen by Utkarsh.


from itertools import permutations
n=int(raw_input())
n=[x for x in range(1,n+1)]
count=0
for i,j,k in permutations(n,3):
    if i<j and j>k:
        count+=1
print count
\$\endgroup\$
  • \$\begingroup\$ Can you please add a link to the contest's page ? \$\endgroup\$ – janos Aug 2 '15 at 21:50
4
\$\begingroup\$

It's a waste to explore the entire permutation space. There's a simpler way to calculate the possible combinations using basic combinatorics principles:

  • One number can be selected from the range 1 .. n
  • One number can be selected from the range 1 .. n-1
  • One number can be selected from the range 1 .. n-2

There are n * (n - 1) * (n - 2) combinations like this, but that includes n in the first, second, and third positions. You need to exclude the combinations where n is in the first and third position, so you need to divide it by 3.

def get_candy_permutations_count(n):
    """
    >>> get_candy_permutations_count(3)
    2
    >>> get_candy_permutations_count(4)
    8
    >>> get_candy_permutations_count(5)
    20
    >>> get_candy_permutations_count(6)
    40
    """
    return n * (n - 1) * (n - 2) // 3

Note the truncating integer division. This is safe to do, as the number of combinations is always necessarily a multiple of 3.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.