C++ Solution for Hackerrank Encryption Challenge

This is not a regular post of mine about a certain mobile topic, this post is about my solution for a general interesting challenge that I found in HackerRank. In this time, I used C++ as an implementation programming language for my solution.

The problem summary is as follows:

“An English text needs to be encrypted using the following encryption scheme. First, the spaces are removed from the text. Let L be the length of this text. Then, characters are written into a grid, whose rows and columns have the following constraints

Finally, the encrypted text is extracted from the grid from its columns. More information and examples about the problem can be found in: https://www.hackerrank.com/challenges/encryption/problem

Approach

My approach is to simply perform the following steps to perform the required encryption:

1. Removing any spaces in the input text.
2. Finding the right lower bound (rows) and the right upper bound (columns).
3. Filling a 2D array (lowerbound X upperbound) with the input text.
4. Extracting encrypted text from the 2D Array in step #3.

Before digging into the solution, I would like to mention that I will skip validating the input string since as per the problem statement, input string is assumed to be a non-empty one.

Removing any spaces in the input text

Simple look for any space in the input string and remove it whenever it is found as shown in the next code snippet.

input.erase(std::remove(input.begin(), input.end(), ‘ ‘), input.end());

Finding the right lower bound (rows) and upper bound (columns)

The next step is to find the right size of rows and columns. If we look into the problem statement, it states the following three rules for rows and columns sizes.

1. rows <= columns.
2. rows X columns >= L (string size)
3. If multiple grids satisfy the above conditions, choose the one with the minimum area.

This can be solved by starting with a lower bound of a value floor(sqrt(L)), and an upper bound of a value ceil(sqrt(L)), then multiplying lower bound by upper bound making sure that they are greater than or equal L. If multiplying lower bound by upper bound is less than L, then we increment lower bound (or) upper bounds making sure that lower bound will be always less than or equal to the higher bound value.

int size = input.length();
int lowerbound = (int) floor(sqrt(size));
int upperbound = (int) ceil(sqrt(size));
int total = upperbound * lowerbound;
 
while (total < size) {
    if (lowerbound < upperbound) {
        ++lowerbound;
    } else {
        ++upperbound;
    }
    total = upperbound * lowerbound;
}

After this step, we can now start creating a 2D array (grid) of (lower bound size X upper bound size ) filling it with the input text to get the desired encrypted value.

Filling a 2D array (lower bound X upper bound) with the input text

This step is simply creating a 2D array of (lower bound size X upper bound size ) filling it with the input text in a row by row manner.

char grid[lowerbound][upperbound] = {0};
int index = 0;
for (int row = 0; row < lowerbound; ++row) {
    for (int col = 0; col < upperbound; ++col) {
        if (index <= input.length() - 1) {
            grid[row][col] = input.at(index);
            ++index;
        }
    }
}

After this step, we can now start extracting the encrypted text from the 2D Array.

Extracting encrypted text from the 2D Array

This step is simple, we create an empty string and fill it out from the 2d array column by column.

string encrypted = "";
for (int col = 0; col < upperbound; ++col) {
    for (int row = 0; row < lowerbound; ++row) {
        if (grid[row][col] != 0) {
            encrypted += grid[row][col];
        }
    }
    
    if (col != upperbound - 1) {
        encrypted += " ";
    }
}

Full source and Results

Attached below the full source code (using C++ 14).

#include <algorithm>
#include <cmath>
#include <fstream>
#include <iostream>
#include <ostream>
#include <string>
using namespace std;
string encryption(string& input) {    
    input.erase(std::remove(input.begin(), input.end(), ' '), input.end());
    int size = input.length();
    int lowerbound = (int) floor(sqrt(size));
    int upperbound = (int) ceil(sqrt(size));
    int total = upperbound * lowerbound;
    
    while (total < size) {
        if (lowerbound < upperbound) {
            ++lowerbound;
        } else {
            ++upperbound;
        }
        total = upperbound * lowerbound;
    }
    
    char grid[lowerbound][upperbound] = {0};
    int index = 0;
    
    for (int row = 0; row < lowerbound; ++row) {
        for (int col = 0; col < upperbound; ++col) {
            if (index <= input.length() - 1) {
                grid[row][col] = input.at(index);
                ++index;
            }
        }
    }
    
    string encrypted = "";
    
    for (int col = 0; col < upperbound; ++col) {
        for (int row = 0; row < lowerbound; ++row) {
            if (grid[row][col] != 0) {
                encrypted += grid[row][col];
            }
        }
        
        if (col != upperbound - 1) {
            encrypted += " ";
        }
    }
    
    return encrypted;
}
int main() {
    ofstream fout(getenv("OUTPUT_PATH"));
    string s;
    
    getline(cin, s);
    string result = encryption(s);
    fout << result << "\n";
    fout.close();
    return 0;
}

Results