# Cognizant GenC Elevate Sample Coding Question 8

## Question 8

In this article, we will discuss about Coding Question with their solution in C++ and java. In this question , we have given a number n and we have to find the total number of dearangements of a set of n elements.

### Question 8

A Derangement is a permutation of n elements, such that no element appears in its original position.
For example, a derangement of {0, 1, 2, 3} is {2, 3, 1, 0}.
Given a number n, find the total number of Derangements of a set of n elements.

Input Specification:
input1: N, the number of Objects

Output Specification:
Return the number of arrangements in which no object occurs at its original
position

Example 1:

Input: n = 2
Output: 1
For two elements say {0, 1}, there is only one possible derangement {1, 0}

Example 2:

Input: n = 3
Output: 2
For three elements say {0, 1, 2}, there are two possible derangements {2, 0, 1} and {1, 2, 0}

Example 3:

Input: n = 4
Output: 9
For four elements say {0, 1, 2, 3}, there are 9 possible derangements {1, 0, 3, 2} {1, 2, 3, 0} {1, 3, 0, 2}, {2, 3, 0, 1}, {2, 0, 3, 1}, {2, 3,1, 0}, {3, 0, 1, 2}, {3, 2, 0, 1} and {3, 2, 1, 0

`#include <iostream>using namespace std;int countDer(int n){	// base case	if (n == 1 or n == 2) {		return n - 1;	}	int a = 0;	int b = 1;	// using above recursive formula	for (int i = 3; i <= n; ++i) {		int cur = (i - 1) * (a + b);		a = b;		b = cur;	}		return b;}// Driver Codeint main(){	int n;	cin>>n;	cout  << countDer(n);	return 0;}`
`import java.util.*;import java.io.*;public class Main {    static int countDer(int n) {                if(n == 1 || n == 2) {            return n-1;        }                int a = 0;        int b = 1;                    for (int i = 3; i <= n; ++i) {            int cur = (i-1)*(a+b);            a = b;            b = cur;        }                        return b;    }        public static void main (String[] args)    {        Scanner sc  = new Scanner(System.in);        int n = sc.nextInt();        System.out.println(""+countDer(n));        }}`