Elly’s Prime Matrix

Happy Fourth of July to our Topcoders in the United States of America!  What is a better way to celebrate freedom than by solving a statistics problem (more specifically a matrix problem)!  Elly’s Prime Matrix was originally a qualification round problem for TCC India 2018.  The solution below follows the outline provided by jeel_vaishnav.  
The problem statement is as follows: Elly has a matrix of digits.  There is a prime number in the matrix, and it can be summoned by taking one digit from each row and concatenating the digits (in the order of first to last).   The solution to the problem involves providing how many prime numbers are possible from the matrix.
The matrix is provided as a String[] to the method getCount() which then returns an int.  The length of the resulting string, m, is provided as the number of rows in the matrix, m.  For example, let us say we have a matrix:


“4,0,6”
“1,1,2”


The possible prime numbers are: 02. Therefore, the number of outputs is 1. If the matrix is constructed as such:


“4,1,6”
“1,0,2”


There are no prime numbers, so the resulting output is 0.
With this in mind, let us start looking at the solution. Let us say that in an unordered_set str_set, we need to find the size of the set. We can:


Code: C++
int ans = str_set.size();


This will return the number of possible prime numbers as the size of the set will be the prime numbers found.
Now let us look at how we will find the prime numbers in the set. The idea is fairly simple. Just take the matrix string and concatenate the numbers together and check if the numbers are prime or not. The numbers that are found to be prime are added to the set.
Pseudocode:


set <string> created_numbers, prime_set;
for (int i = 0; i < num_rows; i++):
string num_str;
for  (int j = 0; j < num_col; j++):
num_str.add(j)
created_numbers.add(num_str)
for (int i = 0; i < created_num.size(); i++):
if(created_num[i] is prime):
prime_set.add(i);
else:
continue


Now that the pseudocode has been written, let us write the code in C++. The code will take advantage of C++’s strings, type casting capabilities, and unordered sets. Note the code has not been compiled and tested.
Code C++:
EllysPrimeMatrix.h:


#include <cstdlib>
#include <iostream>
#include <fstream>
#include “string.h”
Class EllysPrimeMatrix{
public:
int getCount(str[] s);
};


EllysPrimeMatrix.cpp:


#include “EllysPrimeMatrix.h”
int EllysPrimeMatrix::getCount(str[] s){
int ans = 0;
char [ ][ ] a = new char[s.length()][ ];
int row = s.length();
for (int i = 0; i < row; ++i){
a[i] = (char) s[i];
}
int column = a[0].length();
int prime[ ] = new int [];
prime[-1] = new int[MAX_INT];
prime[0] = -1;
for (int i = 2; i < MAX_INT-1; ++i){
if (prime[i] == 0){
for (int j = i; j <= MAX_INT-1; j ++)
{
prime[j] = i;
}
}
}
unordered_set <int> prime_set = new unordered_set<>();
set.add(0);
for (int i = 0; i < row; ++i){
unordered_set <int> new_set = new unordered_set<>();
for (int j = 0; j < column; ++j){
for (int k = 0; k < prime_set.size(); ++k){
int val = k * 10 + (a[i][j] - ‘O’);
new_set.add(val);
}
prime_set = new_set;
ans = prime_set.size();
}
}
return ans;
}


The original answer was written in Java.  Be sure to catch the next SRM that will occur on July 9th.  Happy Fourth of July and happy coding!