C程序在一系列数字中找到缺失的整数

Question

给出一系列n-1个不同的正整数,所有这些整数都小于或等于整数'n'.你必须找到范围[1,2,...,n]中缺少的整数.在不使用数组的情况下解决问题.

输入格式:包含整数'n'的一行,其中2 <= n <= 10,000第一行后跟一系列'n-1'个不同的正整数.请注意,序列可能没有任何特定顺序.

我通过使用数组获得了代码

#include<stdio.h>
int main()
{
 int i,j,n[9999],m,t;
 scanf("%d",&m);
 for(i=1;i<m;i++)
  {
   scanf("%d",&n[i]);
  }
 for(i=1;i<m;i++)
  {
   for(j=1;j<i;j++)
    {
      if(n[j]>n[j+1])
       {
         t=n[j];
         n[j]=n[j+1];
         n[j+1]=t;
        }
    }
   }
   for(i=2;i<m;i++)
    {
     if(n[i-1]!=n[i]-1)
       {
          printf("%d",n[i]-1);
          break;
       }
  }
 return(0);
 }

如何在不使用数组的情况下执行相同操作？

Answer 1

逻辑很简单.您只需找到给定n的连续数字的总和.

并且,现在添加问题中提供的所有数字,以找到给定数字的总和.

区别在于你可以说这两个总和之间的差异是缺失的数字.

例如: - 比方说,n = 6.

所以,你只能找到从1开始的n个连续整数之和,...,6是: - 6*(6 + 1)/ 2 = 21.从1开始的n个连续整数之和的公式是{n*( n + 1)}/2.

并且,现在找到给定n-1个数的总和.

比如,给出的数字是1,2,4,5,6.然后他们的总和= 1 + 2 + 4 + 5 + 6 = 18.

因此,缺失数=连续n个数的和 - 给定(n-1)个数之和= 3.

Answer 2

找到给定整数的总和.从n(n + 1)/ 2中减去它.

说明:前n个整数的和为n(n + 1)/ 2.因此,给定整数的总和+缺失整数= n(n + 1)/ 2.

假设n = 10;

然后,1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 10*(10 + 1)/ 2 == 55

如果给定的整数是-1,2,3,4,5,6,7,8,10.

然后回答= 55 - (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 10)= 9.