Найти недостающее число в последовательности, не отсортированной

Question

Мне нужно найти недостающее число в последовательности, не отсортированной. Эта последовательность хранится в объекте String. Например, в этой последовательности: 3 1 6 5 2 недостающее число - 4. Между каждым номером есть \n. Я должен сделать это, не используя структуры как Array, Dictionary, Lists и т. Д., Потому что мне нужно иметь сложность O (1). На входе я получаю также максимальное число последовательности (в последовательности примеров, я получаю номер 6) Любая идея?

Answer 1

МЕТОД 1 (Использовать формулу сумма) Алгоритм:

1. Получить сумму чисел всего = п * (п + 1)/2 ----------- O (1)

2 Вычесть все числа от суммы и вы получите недостающее число

void ans(int total){  ///O(1) 

      big_total = (n+1)*(n+2)/2; // n+1 because 1 number is missing 

      return (big_total-total); 


    } 




input_array() 
{ 
    int n,total=0,i; 

    cout<<"enter no of element"; 
    cin>>n; 
    for(i=0;i<n;i++) 
    { 
    cin>>arr[i]; 
    total+=arr[i]; 
    } 

    cout<<ans(total); 

}