Double sum optimization

Question

Recently I got this question in one of my interviews, which I unfortunately skipped, but I'm very curious to get the answer. Can you help me?

int sum = 0;
int num = 100000000;
for (int i = 0; i < num; i++){
    for (int j = 0; j < num; j++ ){
        sum += m_DataX[i] * m_DataX[j];
    }
}

EDITED: Also I would like to see if it is possible to optimize if we have the following expression for sum:

sum += m_DataX[i] * m_DataY[j];

Answer 1

Simply, square of sum of the numbers. Why?

Let, an array is, |1|2|3|

Then, the code produces

1*1 + 1*2 + 1*3
2*1 + 2*2 + 2*3
3*1 + 3*2 + 3*3

That is,

(1*1 + 1*2 + 1*3) + (2*1 + 2*2 + 2*3) + (3*1 + 3*2 + 3*3)

=>1(1+2+3) + 2(1+2+3) + 3(1+2+3)

=>(1+2+3)*(1+2+3)

Therefore, the code will be

int tempSum = 0;
for (int i = 0; i < num ; i ++){
   tempSum+=m_DataX [i];
}

sum=tempSum*tempSum;

Update:

What if, sum += m_DataX[i]*m_DataY[j]

Let, two arrays are, |1|2|3| and |4|5|6|

Therefore,

1*4 + 1*5 + 1*5
2*4 + 2*5 + 2*6
3*4 + 3*5 + 3*6

=> 1*4 + 2*4 + 3*4 + 1*5 + 2*5 + 3*5 + 1*6 + 2*6 + 3*6 => (1+2+3)*(4+5+6)