Advertisement
bogolyubskiyalexey

Found 2 missed numbers

Jul 15th, 2019
206
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.54 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using ui32 = uint32_t;
  5.  
  6. std::pair<ui32, ui32> solve(ui32 n, const std::vector<ui32>& v) {
  7.     // найдем missedNumbersXor - xor потеярнных чисел
  8.     ui32 allNumbersXor = 0;
  9.     for (ui32 i = 0; i <= n; ++i) {
  10.         allNumbersXor ^= i;
  11.     }
  12.     ui32 numbersXor = 0;
  13.     for (auto number : v) {
  14.         numbersXor ^= number;
  15.     }
  16.  
  17.     ui32 missedNumbersXor = allNumbersXor ^ numbersXor;
  18.  
  19.     // находим selectedBit - любой бит, в котором различаются потерянные числа
  20.     ui32 selectedBit = 0;
  21.     for (ui32 bit = 0; bit < 32; ++bit) {
  22.         if ((1 << bit) & missedNumbersXor) {
  23.             selectedBit = bit;
  24.             break;
  25.         }
  26.     }
  27.  
  28.     // находим одно из потерянных чисел  у которого указанный бит равен 1 и далее получаем второе потерянное число
  29.     ui32 allNoZeroBitNumbersXor = 0;
  30.     for (ui32 i = 0; i <= n; ++i) {
  31.         if ((1 << selectedBit) & i) {
  32.             allNoZeroBitNumbersXor ^= i;
  33.         }
  34.     }
  35.     ui32 noZeroBitNumbersXor = 0;
  36.     for (auto number : v) {
  37.         if ((1 << selectedBit) & number) {
  38.             noZeroBitNumbersXor ^= number;
  39.         }
  40.     }
  41.  
  42.     ui32 first = allNoZeroBitNumbersXor ^ noZeroBitNumbersXor;
  43.     ui32 second = missedNumbersXor ^ first;
  44.     return { first, second };
  45. }
  46.  
  47. int main() {
  48.     ui32 n;
  49.     std::cin >> n;
  50.     std::vector<ui32> v(n - 1, 0);
  51.     for (ui32 i = 0; i < n - 1; ++i) {
  52.         std::cin >> v[i];
  53.     }
  54.     std::pair<ui32, ui32> answer = solve(n, v);
  55.     std::cout << answer.first << " " << answer.second << std::endl;
  56. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement