在未排序的序列中查找缺少的編號

Question

我必須在未排序的序列中找到缺失的編號。這個序列存儲在一個String對象中。例如，在此序列中：3 1 6 5 2缺少的編號是4。 每個數字之間都有一個\n。我必須這樣做，而不使用數組，字典，列表等結構，因爲我需要具有O（1）複雜性。 在輸入我也收到序列的最大數量（在示例序列中，我收到數字6） 任何想法？

Answer 1

方法1（用求和公式） 算法：

1. 獲取數字 的總和= N *（N + 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); 

}