My algorithm is correct, but some results are wrong? (C++)

Question

So I took this practice lesson called 'permMissingElement' on www.codility.com, and here is my code:

#include <iostream>

using namespace std;

int solution(vector<int> &A)
{
    int N = A.size();
    double Nf = double(N);
    int n;
    double missingf;

    int missing;
    double sumN1, sumN2;
    int sum = 0;
    double sumf;
    double two = 2.0;

    for (n = 0; n < N; n++)
    {
        sum = sum + A[n];
    }

    sumf = double(sum);
    sumN1 = (Nf+double(1.0))/double(2.0);
    sumN2 = sumN1*(Nf+double(2.0));
    missingf = sumN2 - sumf;
    missing = int(missingf);
    return missing;
}

Now, here is the problem. My algorithm works, but for some reason I cannot figure out, gives wrong answers on "large" values of N. (N can be a maximum of 100,000 in the lesson).

Anyway, I initially wrote the program using all ints, and then realized maybe I was getting an overflow because of that, so I changed them to doubles, but I still get wrong answers on large values of N... why is that?

Thanks

`double` does not have infinte precision either, and it can introduce rounding errors as well. And please format your code before posting. Also, the results seems to be dependent on the limits of the elements of A. — Csq, Jun 05 '14 at 12:05
Please specify "wrong results". For what input? What do you expect? Why? What are you getting instead? — John Dvorak, Jun 05 '14 at 12:07
You could try `long long` (or `unsigned long long` if your algorithm only needs unsigned values), which would buy you some range, but eventually it would fail if the numbers are too large. — juanchopanza, Jun 05 '14 at 12:07
@Csq I already said in the question the limit of the elements is 100,000. — TheGrapeBeyond, Jun 05 '14 at 13:28
@JanDvorak I cant specify. The problem is that the evaluation program they have just says "Fail for large N". That's all the information I have. If I knew, I probably would not be posting here. — TheGrapeBeyond, Jun 05 '14 at 13:29
Wow! What the hell? All those downvotes, but no reason given. SO says to say why you downvoted so that question can be improved. What the hell? — TheGrapeBeyond, Jun 05 '14 at 13:32
@juanchopanza Thanks! That worked. If you put it as an answer it would be good. — TheGrapeBeyond, Jun 05 '14 at 15:17
Can you put comments in your code so people understand what is is you need? — T.S., Jun 30 '14 at 20:00

score 1 · Answer 1 · edited May 23 '17 at 10:26

Doubles are floating point numbers, which means you are guaranteed to lose precision, especially for large numbers. Instead of using int use another integral type like long or long long.

The C++ standard doesn't specify an exact size for each type, but an int is at least 16 bits, a long is at least 32 bits and a long long at least 64 bits.

Check this SO question for more pointers: size of int, long, etc

score 1 · Answer 2 · answered Jun 05 '14 at 13:56

1

Interesting approach you have there, I solved the same problem in php using the following algorithm, interpreting each array value as an index, then inverting the value. The position of the last value>0 is the missing one, and it still runs in O(n). That way you avoid the overflow adding big numbers, as you do not have to add anything.

error_reporting(0);
$s = count($A); 
for ($i=0; $i<$s; $i++)
{
    $n = abs($A[$i])-1;
    $A[$n]*=(-1);
}
for ($i=0; $i<$s; $i++)
{
if ($A[$i]>0)
        return $i+1;
}
return $s+1;

answered Jun 05 '14 at 13:56

sibi

39
6

Interesting! I do not know perl, but I will try to decode it. Also, why are you taking abs(), isnt that superfluous? In the problem, I think they only consider elements in the range 1 to 100,000, so always positive. Just wondering. Ill analyze your answer. Thanks! – TheGrapeBeyond Jun 05 '14 at 14:00
I tried an approach that did not need the abs(), – sibi Jun 06 '14 at 07:17
I tried an approach that did not need the abs(), but this turned out to be easier. By interpreting the value of each array entry as an index $n (-1 because of the range 1 to 100.000), then inverting the value at position $n, I still know the original value, which is abs() of it. That value is most likely still needed, because it may point to another element that has not yet been visited. Btw, it is php, not perl. – sibi Jun 06 '14 at 07:27

My algorithm is correct, but some results are wrong? (C++)

2 Answers2