Please login

Prime

Prepinsta Prime

Video courses for company/skill based Preparation

(Check all courses)
Get Prime Video
Prime

Prepinsta Prime

Purchase mock tests for company/skill building

(Check all mocks)
Get Prime mock

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

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));

}
}