对于非常大的输入，丢失并重复从1 ... n开始的数字数组。使用1 ... n系列属性的解决方案。溢出问题

Question

这是同一网站为https://www.interviewbit.com/problems/repeat-and-missing-number-array/提供的代码：

vector<int> repeatedNumber(const vector<int> &V) {
   long long sum = 0;
   long long squareSum = 0;
   long long temp;
   for (int i = 0; i < V.size(); i++) {
       temp = V[i];
       sum += temp;
       sum -= (i + 1);
       squareSum += (temp * temp);
       squareSum -= ((long long)(i + 1) * (long long)(i + 1));
   }
   // sum = A - B
   // squareSum = A^2 - B^2 = (A - B)(A + B)
   // squareSum / sum = A + B
   squareSum /= sum;

   // Now we have A + B and A - B. Lets figure out A and B now. 
   int A = (int) ((sum + squareSum) / 2);
   int B = squareSum - A;

   vector<int> ret;
   ret.push_back(A);
   ret.push_back(B);
   return ret;
}

现在，我编写了一个类似的代码但没有进行类型转换，它返回了较大输入的错误。任何人都可以解释类型转换如何解决溢出？

此外，我看到了这个问题的XOR方法，但我不知道位操作问题。如果有人可以使用位操作方法帮助我处理问题的链接/资源，那将是很棒的！

感谢您阅读我的问题并希望提供帮助！干杯!

Answer 1

(i + 1) * (i + 1)将在int算术中进行评估，具有溢出的可能性，其行为未定义。

写作

((long long)(i + 1) * (long long)(i + 1)); 

是一种消除这种影响的冗长方式;你可以使用更清晰的

(i + 1LL) * (i + 1)

而是导致其他条款的转换。