C++

Forum

 
Missing element

Pages: 12
frek (576)
Here's the exercise:

An array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.

Your goal is to find that missing element.

Write a function:

int solution(vector<int> &A);

that, given an array A, returns the value of the missing element.

For example, given array A such that:

A[0] = 2
A[1] = 3
A[2] = 1
A[3] = 5
the function should return 4, as it is the missing element.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..100,000];
the elements of A are all distinct;
each element of array A is an integer within the range [1..(N + 1)].

I wrote this with time complexity O(N):

1
2
3
4
5
6
7
8
9
 
#include <algorithm>
#include <numeric>

int solution(vector<int> &A) {
    auto N = A.size() + 1;

    return N * (N + 1) / 2 -
    std::accumulate(A.begin(), A.end(), 0);
}


1) Any comments, please?
2) std::accumulate exists in <algorithm>. Does including <numeric> too, have any effect on the code, please?
Last edited on
salem c (3700)
lastchance (6980)
std::accumulate exists in <numeric>
It DOESN'T exist in <algorithm>

Not sure, but your summation method may also overflow what can be stored in an int.
Last edited on
Peter87 (11235)
lastchance is right, you should worry about overflow. If N=100000 then N * (N + 1) / 2 is 5000050000 which does not fit in a 32-bit integer type.
frek (576)
Yeah, right. I should have used unsigned long N instead.
seeplus (6591)
unsigned long is only 32 bit - with a max value of 4,294,967,295 - which is still less than 5,000,050,000. A 64-bit value is needed - uint64_t which has a max value of 18,446,744,073,709,551,615
Peter87 (11235)
long might be 32 or 64 bits depending on your compiler/platform.

Note that it's not just the type of N that you need to watch out for. Your call to std::accumulate will return an int because the third argument is an int.
seeplus (6591)
Yes. The third argument should be 0ull.
frek (576)
So I should have used the algorithm this way, right?

1
2
3
4
5
6
7
8
9
 
#include <algorithm>
#include <numeric>

int solution(vector<int> &A) {
    uint64_t N = A.size() + 1;

    return N * (N + 1) / 2 -
    std::accumulate(A.begin(), A.end(), 0ull);
}
keskiverto (10402)
Now you have both uint64_t and unsigned long long values in your expression. Not an error, but you could be more systematic.
frek (576)
Aren't they the same, or don't have the same length/size? I guess both have 8 bytes length (all positive)
MikeyBoy (5631)
Hence "Not an error, but you could be more systematic", I guess.

Not for the first time, I would encourage you to read posts more carefully.
DizzyDon (121)
Since unsigned long is only guaranteed to be 32-bits, it is in fact an error to use it.
Peter87 (11235)
Unfortunately there are no fixed-width integer literals. You would have to cast the value to the correct type or create your own user-defined literals if you don't want to mix types. Not that I think it really matters here since both types are large enough and conversion between them won't lead to any surprises.

unsigned long long and uint64_t are usually the same size (and even the same type).

According to the C++ standard unsigned long long is only guaranteed to be at least 64 bits. It means it might be larger than 64 bits, but not sure if that's the case anywhere though.

uint64_t is guaranteed to be exactly 64 bits. If the hardware makes it impossible to support this type (which would be extremely unusual) then it will simply not be available.
Last edited on
frek (576)
Thank you Peter for your info.
Do you have a "complete" table to show what you expressed in your post? That may be very helpful for me to learn more in this case?

>If the hardware makes it impossible to support this type
Could you please explain this section a little more?
seeplus (6591)
Perhaps:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
#include <numeric>
#include <vector>
#include <iostream>

auto solution(const std::vector<int>& A) {
    const auto sum {std::accumulate(A.begin(), A.end(), 0ull)};
    const decltype(sum) N {A.size() + 1}, S {N % 2 ? (N + 1) / 2 * N : N / 2 * (N + 1)};

    return S - sum;
}

int main() {
    const std::vector<int> vi {1, 2, 4, 5, 6};

    std::cout << solution(vi) << '\n';
}



3


where the / 2 is done before the * on the even number of N or N + 1.
Last edited on
DizzyDon (121)
You're assuming int is 32-bits! And even if it is 32-bits, it should be unsigned since half of 5000050000 is 2500025000 which is larger than than MAX_INT (if int is 32-bits), which is 2147483647.
Last edited on
Peter87 (11235)
frek wrote:
Do you have a "complete" table to show what you expressed in your post? That may be very helpful for me to learn more in this case?

Look here: https://en.cppreference.com/w/cpp/language/types#Properties

... and char is at least 8 bits ...

char is never bigger than short.
short is never bigger than int.
int is never bigger than long.
long is never bigger than long long.


>If the hardware makes it impossible to support this type
Could you please explain this section a little more?

The C++ standard gives quite a lot of room for weird hardware that are rare or might not even exist. The C++ standard doesn't even require a byte to be 8 bits, it could be more. If for example a byte was 9 bits there would be no way to have a type that is exactly 64 bits. Seven 9-bit bytes would give you 63 bits. Eight 9-bit bytes would give you 72 bits. That's why the fixed-width integer types are "optional" and not guaranteed to be available.
Last edited on
deleted account xyzzy (5768)
That properties table shows types of data models commonly used by a compiler implementation, something I've personally run across using GCC vs. MSVC.

https://en.cppreference.com/w/cpp/language/types#Data_models

The integer types are the same between the compilers, the bits/bytes with floating point types can vary.
lastchance (6980)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
#include <iostream>
#include <vector>
using namespace std;

int solution( vector<int> &A )
{
   int result = A.size() + 1;
   for ( int i = 0; i < A.size(); i++ ) result ^= A[i] ^= ( i + 1 );
   return result;
}

int main()
{
   vector<int> V = { 1, 2, 4, 5, 6 };
   cout << solution( V );
}
Pages: 12