İtkin nömrəni tapın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg Capital One Cisco eBay Facebook Goldman Sachs google IBM microsoft Nvidia Kahin PayPal XidmətNow Yandex
Arista Networks GeyimBaxılıb 771

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;
}

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();
        }
        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

İ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. Xor dəyərlərini saxlamaq üçün yalnız bəzi dəyişənlərdən istifadə edin.

References

Translate »