that was my first answer. the interviewer pointed out that even if n fit within an int, there was no guarantee that n^2 would. my immediate second thought was to multiply every even number by -1, but i realised that you could always provide an input that would make that overflow too.
Here, I coded this for you - http://codepad.org/kdqoLXFA (scroll down for the output! it's not just a pastebin but runs it for you). As you can see my code contains tests at the end to show it's working, but not a robust testing class because it's a brittle piece of shit. I don't even want to know what it would do with input that doesn't meet its promises.
I also Googled this and an alternative (that admittedly I did not think of) given such tight restraints is to keep a running bitwise xor of your elements, and also bitwise xor'ing in (1..n) similar to the above - then you don't need to do it from a head and a tail, at the end rather than a difference you just end up with the missing number. This is probably superior to what I just coded.
But both algorithms are really stupid and really brittle. Sorting is fast and there is no reason not to do it that way.
i like the idea of subtracting from either the head or the tail of a virtual list too; that's clever :)
With the xor solution, on the other hand, you don't really have that option -- if the input does not exactly match the input condition, then it WILL return whatever - with no indication that anything is amiss. Even slightly wrong input will give unpredictable, completely wrong output with no indication that anything is wrong.
What's worse is that it's trivial to game: as an exercise try making a malicious generator that takes an n of at least 4 and Target number, and returns (generates) an array (of size n-1) for feeding the XOR solution that shall get the xor solution to output the Target as the missing number. Further, the malicious generator, instead of generating an array with one missing number, actually shall generate a list which is as close to correct as possible, except that it shall (as an extra 'fuck you') in all cases contain the "Target" value -- twice.
btw thanks for the feedback on the sum thing :)