Apply For Jobs
Get Hiring UpdatesCognizant 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 Code
int 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));
}
}
