If this would have been true, he would have asked about Gauss (it's one of the most famous math tricks in highschool afterall). he didn't ask, op didn't know ei

If this would have been true, he would have asked about Gauss (it's one of the most famous math tricks in highschool afterall). he didn't ask, op didn't know either. so I would have suspected cheating. op's answer is constant n, but could have been improved to n/2 on average with a hash table. (but some constant overhead). so it really depends on the size of n.