QUESTION:-
Sejal Shukla is a cute Computer Science and Engineering student at Imperial College Of Engineering and Technology. Once the college has organized a workshop where students can participate to learn to hack. Participants were given questions based on encryption of a secret message to check their hacking skills. Sejal was very poor in hacking and programming hence she needs help. We expect you to help her, provided she is single and cute.
The problem is, every participant is going to get some T numbers of secret messages to crack. Each secret message has a number(an integer) and we have to check two conditions.
i. If the number can be written as the product of two different prime integers less than it.
ii. If the number can be written as the sum of two different prime integers less than it.
If the above conditions are satisfied then the output will be as follows.
INPUT
v First Line contains T, i.e. the number of secret messages the participants is going to get.
v Each line of the next T lines contain an integer(<105).
OUTPUT
v If both of the conditions are satisfied then output the corresponding alphabets for the even digit.(1234 → 1B3D)
v If one of the conditions are satisfied then output the corresponding alphabets for the odd digits. (1234 → A2C4)
v If none of the conditions is satisfied then output “NO” (Without the double quote).
CORRESPONDING ALPHABET LIST:-
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
A
|
B
|
C
|
D
|
E
|
F
|
G
|
H
|
I
|
TEST CASES:-
INPUT
5
6
4
24
12345
24689
OUTPUT
F
NO
B4
A2C4E
B4F8I
Ans:-
1. prerequisites - Knowledge of prime numbers and semiprime natural numbers.
2. Explanation -
A semiprime natural number is a number which is the product of two prime numbers. In this question, the first condition gives rise to the set of natural numbers which is a subset of semiprime numbers (excluding the square of the prime numbers less than it). Which means though 25 and 49 are semiprime numbers they are the product of the same prime numbers, hence the first condition doesn’t satisfy for 25 and 49. The first condition requires to check if the given number is the product of two different prime numbers.
Suppose we are given a number n. We can write n = √n×√n. So if we take two loop counters i and j and if one of them is less than √n, then definitely the other one is greater than √n. Hence we can iterate and check for both loops, one less than √n and another one greater than √n, excluding √n.
To output alphabets, we use a simple array of size 9 (as the maximum size is 109) and type “char” Containing the corresponding alphabets as given in the table as it’s elements. The later output is done by iterating over the loop and checking for even and odd positions in two different functions.
C++ Code :-
#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
bool is_prime(ll n);
bool check_prod_condition(ll num); /// To check the first condition i.e. if the number is the
/// product of two different prime numbers
bool check_sum_condition(ll num); /// To check the first condition i.e. if the number is the
/// sum of two different prime numbers
int length_of_number(ll num);
char print_alphabet(ll n);
void convert_even_digit(ll num);
void convert_odd_digit(ll num);
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll num,t;
cin >> t;
for(int i=0;i<t;i++)
{
cin >> num;
if((check_prod_condition(num)==true)&&(check_sum_condition(num)==true))/// If both the condition satisfies
{
convert_even_digit(num);
}
else if(((check_prod_condition(num)==true)&&(check_sum_condition(num)==false))||
((check_prod_condition(num)==false)&&(check_sum_condition(num)==true))) /// If only one condition satisfies
{
convert_odd_digit(num);
}
else
{
cout << "NO" << endl;
}
}
return 0;
}
bool is_prime(ll n)
{
if (n <= 1)
{
return false;
}
if (n <= 3)
{
return true;
}
if (n%2 == 0 || n%3 == 0)
{
return false;
}
for (ll i=5; i*i<=n; i=i+6)
{
if (n%i == 0 || n%(i+2) == 0)
return false;
}
return true;
}
bool check_prod_condition(ll num)
{
ll flag=0;
for(ll i=2;i*i<num;i++)
{
for(ll j=num-1;j*j>num;j--)
{
if(i*j==num)
{
if((is_prime(i)==true) && (is_prime(j)==true))
{
flag++;
break;
}
}
}
}
if(flag>0)
{
return true;
}
else
{
return false;
}
}
bool check_sum_condition(ll num)
{
ll flag = 0;
for(ll i=2;i<=(num/2);i++)
{
for(ll j=num-1;j>(num/2);j--)
{
if(i+j==num)
{
if((is_prime(i)==true) && (is_prime(j)==true))
{
flag++;
break;
}
}
}
}
if(flag>0)
{
return true;
}
else
{
return false;
}
}
int length_of_number(ll num)
{
int count=0;
for(;num;num/=10)
{
count++;
}
return count==0 ? 1 : count;
}
char print_alphabet(ll n)
{
char alphabet[9]={'A','B','C','D','E','F','G','H','I'};
return alphabet[n-1];
}
void convert_even_digit(ll num)
{
ll length = length_of_number(num);
ll digit[length];
for(ll i=length-1;i>=0;i--)
{
digit[i]=num%10;
num = num/10;
}
for(ll i=0;i<length;i++)
{
if((i+1)%2==0)
{
cout << print_alphabet(digit[i]);
}
else
{
cout << digit[i];
}
}
cout << endl;
}
void convert_odd_digit(ll num)
{
ll length = length_of_number(num);
ll digit[length];
for(ll i=length-1;i>=0;i--)
{
digit[i]=num%10;
num = num/10;
}
for(ll i=0;i<length;i++)
{
if((i+1)%2!=0)
{
cout << print_alphabet(digit[i]);
}
else
{
cout << digit[i];
}
}
cout << endl;
}
Hope that helps, keep coding :)
Comments
Post a Comment