DEV Community

loading...
Cover image for Construct the Cypher string based on the given conditions
eduAlgo

Construct the Cypher string based on the given conditions

abhijit2505 profile image Abhijit Tripathy ・3 min read

Given a number N, the task is to convert the given number into a Cypher string on the basis of below conditions:

  • If N is a semiprime, then change every digit at even places of N to it’s corresponding matched alphabet as shown below.
  • If N can be written as a sum of two primes, then change every digit at odd places of N to it’s corresponding matched alphabet as shown below.
  • If both the condition satisfy the concatenate the above two strings formed.
  • If N can’t satisfy the above three criteria, then print “-1”. Below is the list of matched character:

Alt Text

Examples:

Input: N = 61
Output: 6B
Explanation:
Since 61 can be expressed as a sum of two primes: 61 = 2 + 59
Therefore, the resultant string after changing the character at even index is “6B”.
Input: N = 1011243
Output: B0B1C4D
Explanation:
Since 1011243 is Semiprime number: 1011243 = 3 * 337081
Therefore, the resultant string after change the character at even index is “B0B1C4D”.

Approach:

  • Check if the given number N is semi prime or not by using the approach discussed in this article. If yes, then do the following:
    • Convert the given number N to string(say str) using to_string() function.
    • Traverse the above string formed and changed the characters at even index as:
str[i] = char((str[i] - '0') + 65)
Enter fullscreen mode Exit fullscreen mode
  • Print the new string formed.
  • Check if the given number N can be expressed as a sum of two prime numbers or not using the approach discussed in this article. If yes, then do the following:
    • Convert the given number N to string(say str) using to_string() function.
    • Traverse the above string formed and changed the characters at odd index as:
str[i] = char((str[i] - '0') + 65)
Enter fullscreen mode Exit fullscreen mode
  • Print the new string formed.
  • If the above two condition doesn’t satisfy then we can’t form Cypher String. Print “-1”.

Below is the implementation of the above approach:

// C++ program for the above approach

#include "bits/stdc++.h"
using namespace std;

// Function to check whether a number
// is prime or not
bool isPrime(int n)
{
    if (n <= 1)
        return false;

    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0)
            return false;
    }

    return true;
}

// Function to check if a prime number
// can be expressed as sum of
// two Prime Numbers
bool isPossibleSum(int N)
{
    // If the N && (N-2) is Prime
    if (isPrime(N)
        && isPrime(N - 2)) {
        return true;
    }
    else {
        return false;
    }
}

// Function to check semiPrime
bool checkSemiprime(int num)
{
    int cnt = 0;

    // Loop from 2 to sqrt(num)
    for (int i = 2; cnt < 2
                    && i * i <= num;
         ++i) {
        while (num % i == 0) {
            num /= i,

                // Increment the count of
                // prime numbers
                ++cnt;
        }
    }

    // If num is greater than 1, then
    // add 1 to it
    if (num > 1) {
        ++cnt;
    }

    // Return '1' if count is 2 else
    // return '0'
    return cnt == 2;
}

// Function to make the Cypher string
void makeCypherString(int N)
{

    // Resultant string
    string semiPrime = "";
    string sumOfPrime = "";

    // Make string for the number N
    string str = to_string(N);

    // Check for semiPrime
    if (checkSemiprime(N)) {

        // Traverse to make Cypher string
        for (int i = 0; str[i]; i++) {

            // If index is odd add the
            // current character
            if (i & 1) {
                semiPrime += str[i];
            }

            // Else current character is
            // changed
            else {
                semiPrime
                    += char(
                        str[i] - '0' + 65);
            }
        }
    }

    // Check for sum of two primes
    if (isPossibleSum(N)) {

        // Traverse to make Cypher string
        for (int i = 0; str[i]; i++) {

            // If index is odd then
            // current character is
            // changed
            if (i & 1) {
                sumOfPrime
                    += char(
                        str[i] - '0' + 65);
            }

            // Else add the current
            // character
            else {
                sumOfPrime += str[i];
            }
        }
    }

    // If the resultant string is ""
    // then print -1
    if (semiPrime + sumOfPrime == "") {
        cout << "-1";
    }

    // Else print the resultant string
    else {
        cout << semiPrime + sumOfPrime;
    }
}

// Driver Code
int main()
{

    // Given Number
    int N = 1011243;

    // Function Call
    makeCypherString(N);

    return 0;
}
Enter fullscreen mode Exit fullscreen mode

Output:

B0B1C4D
Enter fullscreen mode Exit fullscreen mode

Discussion (0)

pic
Editor guide