ash -4 years ago 84

C++ Question

Given a number 'n', I want to return a sorted array of n^2 numbers containing all the values of k1*k2 where k1 and k2 can range from 1 to n.

For example for n=2 it would return : {1,2,2,4}.(the number are basically 1*1,1*2,2*1,2*2).

and for n=3 it would return : {1,2,2,3,3,4,6,6,9}.

(the numbers being : 1*1, 2*1, 1*2, 2*2, 3*1, 1*3, 3*2, 2*3, 3*3)

I tried it using sort function from c++ standard library, but I was wondering if it could be further optimized.

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

Well, first of all, you get `n^2`

entries, the largest of which will be `n^2`

, and of the possible value range, only a tiny amount of values is used for large `n`

. So, I'd suggest a counting approach:

- Initialize an array
`counts[]`

of size`n^2`

with zeros. - Iterate through your array of values
`values[]`

, and do`counts[values[i]-1]++`

. - Reinitialize the
`values`

array by iterating through the`counts`

array, dropping as many values of`i+1`

into the`values`

array as`counts[i]`

gives you.

That's all. It's `O(n^2)`

, so you'll hardly find a more performant solution.

Recommended from our users: **Dynamic Network Monitoring from WhatsUp Gold from IPSwitch**. ** Free Download**

Latest added