Question

You are an analyst at the Central Intelligence Agency (CIA). You are assigned the job of developing a program that will analyze possible passwords that are used to encrypt password - protected data. The CIA uses a very specific set of rules for passwords to identify non - CIA operatives who attempt to access password - protected data (these non -CIA operatives will try passwords that do not conform to CIA rules). The rules are complicated enough that the CIA has assigned you the job of developing a program that generates all valid passwords. CIA personnel will then use the program to make sure the passwords they select to protect data conform to the rules. The rules that your program must use to determine if the password is valid are as follows: 1. The password must be an integer greater than or equal to 100,000 and less than 1,000,000 2. All the digits in the number have to be unique. 3. The sum of the digits must be a prime number. 4. The permutation of the left - most digit (n) and the smallest digit (k) must be odd - for example: in 645923, the left - most is 6 and the smallest digit is 2. n! / (n - k)! Where the ! denotes a factorial. For example, for the number 645923, the permutation with n = 6 and k = 2 is: 6 * 5 * 4 * 3 * 2 * 1 / (4 * 3 * 2 * 1) = 30. You will list all valid passwords. In addition, you will need to list the total number of valid passwords at the end.

Using C++

Answer 1

This program makes use of just one function apart from main(), called fact() which is a recursive function to calculate the factorial of a number (used in calculating the permutation) All the checks are done within main() itself. If you wish you can separate the different checks into different functions.

The list of valid passwords is not stored anywhere, it is just displayed as and when a valid password is found. If you wish, you may use a vector or a list, etc to store this list of passwords.

Below is code:-

#include <iostream>
#include <cmath>

using namespace std;

//recursive function to calculate and return a factorial
int fact(int num)
{
if(num>1)
return num*fact(num-1);
else
return 1;
}

int main()
{
int validPwdCount=0; //number of valid passwords
for(int i=100000;i<1000000;i++) //this is the range of valid passwords
{
int pwd=i;
bool isValid=true; //make this false if password is invalid
//first check if all digits are unigue
int digits[6]; //save all digits in this array, the password is a 6 digit integer
int index=5;//start filling array from the last position as we'll get the last digit first
while(pwd)
{
digits[index]=pwd%10;//separate each digit and fill in array
pwd/=10;
index--;
}
for(int j=0;j<6;j++)
{
for(int k=0;k<6;k++)
{
if(j!=k) //indices are not equal (not the same number)
if(digits[j]==digits[k])
{
isValid=false;
break;
}
}
if(!isValid) break; //no need to continue looping for duplicate digits if password is invalid
}
if(!isValid) continue; //no need to go ahead for other checks if password is invalid, so continue with outer loop
//and check the next password

//now check if the sum of digits is a prime number
//get sum of digits
long sum=0;
for(int l=0;l<6;l++)
sum+=digits[l];
//check if the sum is a prime number by dividing it by numbers from 2 to square root of the sum
for(int l=2;l<sqrt(sum);l++)
if(sum%l==0) //number is not prime
{
isValid=false;
break; //no need to continue looping for divisors if password is invalid
}
if(!isValid) continue; //no need to go ahead for other checks if password is invalid, so continue with outer loop
//and check the next password

//check if permutation of the left-,ost digit with the smallest digit is odd
int n=digits[0]; //leftmost digit
int k=1000000; //k will hold the smallest digit
for(int l=0;l<6;l++)
if(digits[l]<k)
k=digits[l];
int perm=fact(n)/fact(n-k); //find the required permutation
//check if the permutation is an odd number
if(perm%2==0)
{//the permutation is not an odd number
isValid=false;
continue; //no need to go ahead for other checks if password is invalid, so continue with outer loop
//and check the next password
}
if(isValid)//if password is valid
{
cout<<i<<endl; //print the password
validPwdCount++; //increment the password count
}
}
cout << "Total Number of valid passwords= "<<validPwdCount<< endl;
return 0;
}

Output (last part only):-

Hope this helps!