Speed up a program to find the minimum Hamming distance I have a solution to the puzzle at https://kattis.csc.kth.se/problem?id=codes.
What can I do to make my algorithm much much faster? What the algorithm does is take an N×K matrix and search for the minimum distance — that is, the least number of 1 for all the products of the matrix and a vector that ranges from 00001 to 11111 (where the top is 2K - 1). 

#include &lt;iostream&gt;

using namespace std;

void DataEntry(int &amp;a, int &amp;b, int** &amp;matrix) {

    cin &gt;&gt; a &gt;&gt; b;

    matrix = new int*[a];

    for (int i = 0; i &lt; a; i++) {
        matrix[i] = new int[b];
    }

    for (int i = 0; i &lt; a; i++) {
        for (int j = 0; j &lt; b; j++) {
            matrix[i][j] = -1;
            cin &gt;&gt; matrix[i][j];
        }
    }

}

int* BinaryAdd(int* a, int* b, int tam) {
    int* c;
    int ac = 0;
    c = new int[tam];

    for (int i = tam - 1; i &gt; -1; i--) {
        c[i] = a[i] + b[i] + ac;
        if (c[i] == 2) {
            c[i] = 0;
            ac = 1;
        } else
            ac = 0;
    }

    return c;
}

int* MultiplyMatrices(int** a, int* b, int tamF, int tamC) {
    int * c;
    c = new int[tamF];
    for (int i = 0; i &lt; tamF; i++) {
        c[i] = 0;
        for (int j = 0; j &lt; tamC; j++) {
            c[i] = c[i] + (a[i][j] * b[j]);
            c[i] = c[i] % 2;
        }
    }
    return c;
}

int MinimumDistance(int* a, int tam) {
    int MD = 0;

    for (int i = 0; i &lt; tam; i++) {
        if (a[i] == 1)
            MD++;
    }
    return MD;
}

int pot(int a, int b) {
    int c = 1;
    for (int i = 1; i &lt; b + 1; i++) {
        c = a * c;
    }
    return c;
}

int main() {
    int t = 0, n = 0, k = 0, d = -1, max = -1;
    int ** lecc;
    int * pro;
    int * sal;
    int * sol;
    int * zero;
    int * uno;
    int * pro1;

    cin &gt;&gt; t;

    for (int p = 0; p &lt; t; p++) {

        DataEntry(n, k, lecc);

        pro = new int[k];
        uno = new int[k];
        sal = new int[n];
        zero = new int[n];

        for (int i = 0; i &lt; k; i++) {
            pro[i] = 0;
        }
        for (int i = 0; i &lt; k - 1; i++) {
            uno[i] = 0;
        }
        uno[k - 1] = 1;

        for (int i = 0; i &lt; n; i++) {
            zero[i] = 0;
        }

        pro1 = BinaryAdd(pro, uno, k);

        pro = pro1;

        max = pot(2, k);

        sal = MultiplyMatrices(lecc, pro, n, k);

        d = MinimumDistance(sal, n);

        for (int i = 0; i &lt; max - 1; i++) {

            sal = MultiplyMatrices(lecc, pro, n, k);

            pro1 = BinaryAdd(pro, uno, k);

            pro = pro1;

            int ad = MinimumDistance(sal, n);

            if (ad &lt; d)
                d = ad;
        }
        cout &lt;&lt; d &lt;&lt; endl;
    }

}


Edit: I give you a sample input and output 

Sample input     Sample output
2
7 4
1 0 0 0
0 1 0 0
0 0 1 0           3
0 0 0 1           0
0 1 1 1
1 0 1 1
1 1 0 1
3 2
1 1
0 0
1 1
Considering that this is meant to be a puzzle, I'll write my review as a sequence of escalating hints.


Everybody who is suggesting the use of threads or std::vector or matrix libraries is on the wrong track! How do you think error correction is implemented in your CD player or hard disk firmware? No threads or matrix libraries there, I assure you.
Don't simulate the computer; use the computer.
All operations are modulo 2.  The puzzle guarantees k ≤ 16. Under these conditions, you can massively parallelize vector dot products. (Think SIMD or AltiVec, except you don't need SIMD or AltiVec.)
I've added the bitwise tag to this question.


I'll conclude with a remark that you've basically written C code.  The only thing that makes it C++ is your use of iostream.  C++ can be much more expressive than that.