All Tracks Algorithms Dynamic Programming Dynamic Programming and Bit Masking Problem

The Ghost Type
Tag(s):

Algorithms, Bitmask, Dynamic Programming, Medium

Problem
Editorial
Analytics

Gengar has got an integer $$N$$. Now using his ghostly powers, he can create the permutation from $$1$$ to $$N$$ of this given number.

Since, he's a special kind of Poke'mon, so he thinks he deserves special permutations. He wants to find the total number of special permutations of length $$N$$, consisting of the integers from $$1$$ to $$N$$.

A permutation is called special if it satisfies following condition:

If Ap & Aq == Ap, then p < q, where p and q are two distinct indices of permutation and A is the permutation itself. "&" denotes the bitwise and operation.

Help Gengar in finding the number of such permutations.

Input format:
The only line of input will consist of a single integer $$N$$ denoting the length of the permutation.

Output format:
Output the total number of special permutations of length $$N$$.

Constraints:
1 ≤ $$N$$ ≤ 20

References:
enter image description here

SAMPLE INPUT
4
SAMPLE OUTPUT
8
Explanation

All the special permutations of length 4 are:
1 2 3 4
1 2 4 3
1 4 2 3
2 1 3 4
2 1 4 3
2 4 1 3
4 1 2 3
4 2 1 3

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

September Easy '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications