İtkin nömrəni tapın

Problem bəyanat

Birdən itkin nömrəni tapmaqda array 1-dən N-ə qədər N-1 ədədləri olan bir sıra verdik. 1-dən N-ə qədər olan bir sıra aralığında bir ədəd əskikdir.

Giriş Formatı

N tam ədədi olan birinci sətir.

N-1 tam ədədi olan ikinci sətir.

Çıxış formatı

Bir sətirdə itkin nömrəni çap edin.

Məhdudiyyətlər

• 2 <= N <= 100000
• 1 <= a [i] <= N

İtkin nömrəni tapmaq üçün yanaşma 1 

Aşağıdakı alqoritmdə göstərildiyi kimi Sadə Riyaziyyat düsturundan istifadə edirik.

Alqoritm

1. 1-dən N-ə qədər olan cəmlərin N * (N + 1) / 2 düsturu ilə verildiyini bilirik. Buna real_sum deyək.

2. Sonra massivdəki elementləri cəmləyirik və itkin_sum adlandıraq.

3. Real_sum və eksik_sum arasındakı fərq, itkin_sumu hesablayarkən əlavə edilmədiyi üçün itkin rəqəmdir.

Həyata keçirilməsi itkin nömrəni tapmaq üçün 

C ++ Proqramı 

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
  int n;
  cin>>n;
  int a[n-1];
  for(int i=0;i<n-1;i++)
  {
      cin>>a[i];
  }
  // sum1 store the sum of 1 to N numbers which is N*(N+1)/2;
  ll sum1=(n*(n+1))/2;
  ll sum2=0;
  for(int i=0;i<n-1;i++)
  {
    //sum of elements present in the array;  
    sum2+=a[i]; 
  }
  cout<<"Missing number is: "<<sum1-sum2<<endl;
  return 0;
}

Java Proqramı 

import java.util.Scanner;

class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n-1];
        for(int i=0;i<n-1;i++)
        {
            arr[i] = sr.nextInt();
        }
        // sum1 store the sum of 1 to N numbers which is N*(N+1)/2;
        int sum1=(n*(n+1))/2;
        int sum2=0;
        for(int i=0;i<n-1;i++)
        {
          //sum of elements present in the array;  
          sum2+=arr[i]; 
        }
        System.out.println("Missing number is: "+(sum1-sum2));
    }
}

7
1 2 3 4 5 7

Missing number is: 6

İtkin Nömrəni Tapmaq üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (N) burada N girişin ilk sətrində verilən dəyərdir. Burada elementlərin cəmini tapmaq üçün verilən massivi təkrarlayırıq.

Kosmik Mürəkkəblik

O (1) çünki burada heç bir köməkçi yerdən istifadə etmirik. Cəmi saxlamaq üçün sadəcə bəzi dəyişənlərdən istifadə edin.

İtkin nömrəni tapmaq üçün yanaşma 2 

XOR əməliyyat konsepsiyasından istifadə edirik.

Bildiyimiz kimi

A xor A = 0 ————- Mülk 1

yəni 2 oxşar elementin xoru sıfırdır.

Həmçinin,

A xor 0 = A ————- Mülk 2

yəni sıfır olan hər hansı bir elementin xor eyni ədədi verir.

Alqoritm

1. 1-dən N-ə qədər olan bütün dəyərlərin XOR-unu hesablayırıq və X olduğunu deyirik.

2. Dizidəki bütün dəyərlərin XOR-unu hesablayırıq və Y olduğunu deyirik.

3. İndi (X xor Y) etdikdə, yalnız bir dəfə gələn itkin say xaricində bütün dəyərləri iki dəfə XORlaşdırırıq. Beləliklə, son dəyər XOR xüsusiyyət 2 tərəfindən itkin rəqəmdən başqa bir şey deyil.

Həyata keçirilməsi itkin nömrəni tapmaq üçün 

C ++ Proqramı 

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
  int n;
  cin>>n;
  int a[n-1];
  for(int i=0;i<n-1;i++)
  {
      cin>>a[i];
  }
  int X = 0,Y = 0;
  for(int i=1;i<=n;i++)
  {
      //XOR of all elements from 1 to N
      X^=i;
  }
  for(int i=0;i<n-1;i++)
  {
      //XOR of all elements in the array
      Y^=a[i]; 
  }
  int missing_Num=X^Y;
  cout<<"Missing number is: "<<missing_Num<<endl;
  return 0;
}

import java.util.Scanner;

class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n-1];
        for(int i=0;i<n-1;i++)
        {
            arr[i] = sr.nextInt();
        }
        int X = 0,Y = 0;
        for(int i=1;i<=n;i++)
        {
            //XOR of all elements from 1 to N
            X^=i;
        }
        for(int i=0;i<n-1;i++)
        {
            //XOR of all elements in the array
            Y^=arr[i]; 
        }
        int missing_Num=X^Y;
        System.out.println("Missing number is: "+missing_Num);
    }
}

9
1 2 3 4 6 7 8 9

Missing number is: 5