Найдите недостающее число от 1..N

Question

В одном из интервью они попросили меня найти пропущенный номер из массива.array будет иметь номер от 1 до N.

Мой подход:

   int main()
   {
      int ar[20];
      int sum = 0;

      int n;

      printf("enter numb of elements\n");
      scanf("%d", &n);
      printf("enter array numbers\n");
      for(int i = 0; i<n;i++){
          scanf("%d", &ar[i]);
          sum +=ar[i];
      }

      printf("missing num=%d", ((n*(n+1))/2)-sum);
   }

Но интервьюер не перезвонил после первого раундаопрос.Я не знаю, что не так с моим подходом.

Answer 1

Некоторые проблемы с вашим кодом:

• Алгоритм неверен (отключен на единицу): если массив содержит все числа от 1 до N, кроме одного пропущенного числа, то он имеет N-1 элементов. Ваш код читает N элементов. (В качестве альтернативы, если массив на самом деле имеет N элементов, тогда целевая сумма составляет (N + 1) * (N + 2) / 2 (сумма чисел от 1 до N + 1), а не N * (N + 1) / 2.)

• Включения отсутствуют (в частности, #include <stdio.h>). Это означает, что вызовы printf / scanf имеют неопределенное поведение.

• int main() должно быть int main(void).

• Ни один из вызовов scanf не проверяет свое возвращаемое значение. Это означает, что ваш код не распознается, когда чтение ввода не удается, что приводит к выводу мусора.

• Если n больше 20, ваш код молча пишет за пределами ar. Это классическое переполнение буфера.

• Предыдущий пункт особенно неудачен, потому что вашему коду даже не нужен массив. Все, что вам нужно сделать с введенными числами, это добавить их в sum, для чего не требуется отдельный массив.

• Ваше форматирование несовместимо с for(int i = 0; i<n;i++){. Почему в for(int и i<n;i++){ нет пробелов, а вокруг i = 0;?

• В зависимости от размера N, n*(n+1) может переполниться.

• В последней строке вывода, созданной вашим кодом, отсутствует завершающий символ новой строки: printf("missing num=%d\n", ...);