Verilmiş bir massivin hər hansı alt hissəsinin cəmi kimi təmsil oluna bilməyən ən kiçik müsbət tam ədədi tapın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Verilənlər bazası Fab Taksi4Sure UHG Optum
GeyimBaxılıb 86

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

Sizə a sıralandı sıra ədədi. Verilən hər hansı bir çoxluğun cəmi kimi təmsil edilə bilməyən ən kiçik müsbət tam ədədi tapmaq lazımdır array.

misal

arr[] = {1,4,7,8,10}
2

İzahat: 2-ni cəm olaraq göstərə biləcək heç bir alt sıra olmadığından.

arr[] = {1,2,3,5,7,9}
28

İzahat: 28-ni cəm olaraq göstərə biləcək heç bir alt sıra olmadığından.

 

Verilmiş massivin hər hansı bir alt cəminin cəmində göstərilə bilməyən ən kiçik müsbət tam ədədi tapmaq üçün alqoritm

1. Set output to 1.
2. From i=0 to i less than n.
  1. Check if arr[i] is less than equal to output.
    1. Update the value of output to the sum of output and arr[i].
3. Return output.

 

Izahat

Verilmiş bir massivin hər hansı alt hissəsinin cəmi kimi təmsil oluna bilməyən ən kiçik müsbət tam ədədi tapınPin

 

 

Bizə sıralanmış bir ədəd sıra verilir. Problem ifadəsi ən kiçik müsbət tam ədədi tapmağı xahiş edir. Bu, verilmiş bir massivin hər hansı alt hissəsinin cəmi kimi təmsil edilə bilməz. Bu həlli xətti olaraq tapa bilərik zaman mürəkkəbliyi O (n). Artıq sıralanmış bir sıra olduğumuza görə. Beləliklə, sifariş və ya rəqəm fərqlərindən narahat olmağımız lazım deyil, buna görə də bunu xətti vaxtda tapa biləcəyik.

Dizini keçəcəyik. Ancaq bundan əvvəl çıxış dəyərini 1-ə təyin edin, çünki ən azı ən kiçik müsbət tam ədəd olacaqdır. 1-dən başlayan bir sıra yoxdursa, sadəcə 1-i bir çıxış dəyəri olaraq qaytaracaq. Beləliklə, çıxış dəyərini 1 olaraq qurduqdan sonra, massivi keçərək. Dizinin ilk elementini götürəcəyik və nəticənin dəyərindən kiçik olub olmadığını yoxlayacağıq. Doğrudursa, nəticə və cari sıra elementinin dəyərini əlavə edəcəyik. Və sonra bunu çıxarmaq üçün saxla. Bir sıra elementinin dəyəri çıxış dəyərlərindən çox olmayana qədər bunu etməyə davam edəcəyik. Sonra döngədən çıxacaq və çıxış dəyərini qaytaracağıq.

Bir nümunə arr [] = {1,4,7,8,10} olaraq götürsək, çıxış = 1 ilə başlayacağıq, ilk elementi götürməyə davam edəcəyik və onun çıxışdan az və ya bərabər olduğunu yoxlayacağıq , doğrudur və çıktı və arr [i] dəyərini əlavə edib çıxışı üçün saxlayacağıq və artıq 2 çıxışı var. Yenidən dəyərləri yoxlayacağıq, amma indi serialdakı hər hansı bir nəticə çıxışa bərabər və ya az deyil, buna görə nəhayət 2 tələb olunan cavabımızdır və onu qaytaracağıq.

Verilmiş bir massivin hər hansı bir alt hissəsinin cəmi kimi təmsil edilə bilməyən ən kiçik müsbət tam ədədi tapmaq üçün kod verin

C ++ kodu

#include<iostream>

using namespace std;

int getSmallestInteger(int arr[], int n)
{
    int output = 1;
    for (int i = 0; i < n && arr[i] <= output; i++)
        output = output + arr[i];

    return output;
}
int main()
{
    int arr[] = {1, 3, 4, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout <<"Smallest positive integer : "<<getSmallestInteger(arr, n);

    return 0;
}
Smallest positive integer : 2

 

Java kodu

class IntegernotSumofSubArray
{
    public static int getSmallestInteger (int arr[], int n)
    {
        int output = 1;

        for (int i = 0; i < n && arr[i] <= output; i++)
            output = output + arr[i];

        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = {1, 3, 4, 5};
        int n = arr.length;
        System.out.println("Smallest positive integer : "+getSmallestInteger (arr, n));
    }
}
Smallest positive integer : 2

 

Mürəkkəblik təhlili

Dizidəki alt cəmi kimi mövcud olmayan ən kiçik müsbət ədədi dəyər tapmaq üçün vaxt mürəkkəbliyi

Bir sıra sadəcə keçdiyimiz zaman, xətti zaman mürəkkəbliyi əməliyyatı edirik. Və burada tək keçiddən başqa bir şey etmədiyimiz üçün xətti bir zaman çətinliyinə sahibik. O (n) hara "N"  massivdəki elementlərin sayıdır.

Dizidəki alt cəm kimi mövcud olmayan ən kiçik pozitiv ədədi dəyər tapmaq üçün yer mürəkkəbliyi

Sadəcə giriş saxlayan tək bir massivimiz var, beləliklə alqoritm də xətti kosmik mürəkkəbliyə malikdir. O (n) hara "N"  massivdəki elementlərin sayıdır.

Crack Sistemi Dizayn Müsahibələri
Translate »