Βρείτε τη μικρότερη θετική ακέραια τιμή που δεν μπορεί να αναπαρασταθεί ως άθροισμα οποιουδήποτε υποσυνόλου ενός δεδομένου πίνακα


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις Βάσεις δεδομένων Fab Ταξί4Sure UHG Optum
Παράταξη

Δήλωση προβλήματος

Σας δίνεται ένα ταξινομημένο πίνακας ακέραιων αριθμών. Πρέπει να βρούμε τη μικρότερη θετική ακέραια τιμή που δεν μπορεί να αναπαρασταθεί ως άθροισμα οποιουδήποτε υποσυνόλου ενός δεδομένου παράταξη.

Παράδειγμα

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

Επεξήγηση: Επειδή δεν υπάρχει υπο-πίνακας που μπορεί να αντιπροσωπεύει το 2 ως άθροισμα.

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

Επεξήγηση: Επειδή δεν υπάρχει υπο-πίνακας που μπορεί να αντιπροσωπεύει το 28 ως άθροισμα.

 

Αλγόριθμος για την εύρεση της μικρότερης θετικής ακέραιας τιμής που δεν μπορεί να αναπαρασταθεί ως άθροισμα οποιουδήποτε υποσυνόλου ενός δεδομένου πίνακα

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.

 

εξήγηση

Βρείτε τη μικρότερη θετική ακέραια τιμή που δεν μπορεί να αναπαρασταθεί ως άθροισμα οποιουδήποτε υποσυνόλου ενός δεδομένου πίνακα

 

 

Μας δίνεται μια σειρά από ακέραιους αριθμούς. Η δήλωση προβλήματος ζητά να βρει τη μικρότερη θετική ακέραια τιμή. Αυτό δεν μπορεί να αναπαρασταθεί ως άθροισμα οποιουδήποτε υποσυνόλου ενός δεδομένου πίνακα. Μπορούμε να βρούμε αυτήν τη λύση γραμμικά χρονική πολυπλοκότητα Επί). Καθώς έχουμε ήδη έναν πίνακα ταξινομημένο. Επομένως, δεν χρειάζεται να ανησυχούμε για τις παραγγελίες ή τις διαφορές αριθμών, γι 'αυτό θα μπορέσουμε να το βρούμε σε γραμμικό χρόνο.

Θα διασχίσουμε τον πίνακα. Αλλά πριν από αυτό ορίσετε την τιμή της εξόδου στο 1, καθώς τουλάχιστον θα υπάρχει ο μικρότερος θετικός ακέραιος. Εάν δεν έχουμε έναν πίνακα που ξεκινά από το 1, τότε απλώς πρόκειται να επιστρέψει 1 ως τιμή εξόδου. Έτσι, μετά τη ρύθμιση της τιμής εξόδου ως 1, διασχίζοντας τον πίνακα. Θα πάρουμε το πρώτο στοιχείο του πίνακα και θα ελέγξουμε εάν είναι μικρότερο ή ίσο με την τιμή της εξόδου. Εάν είναι αλήθεια, τότε θα προσθέσουμε την τιμή της εξόδου και του τρέχοντος στοιχείου πίνακα. Και μετά αποθηκεύστε το στην έξοδο. Θα συνεχίσουμε να το κάνουμε αυτό έως ότου η τιμή ενός στοιχείου πίνακα δεν θα υπερβεί τις τιμές εξόδου. Τότε θα βγει από το βρόχο και θα επιστρέψουμε την τιμή της παραγωγής.

Εάν πάρουμε ένα παράδειγμα ως arr [] = {1,4,7,8,10}, θα ξεκινήσουμε με την έξοδο = 1, θα συνεχίσουμε να παίρνουμε το πρώτο στοιχείο και να ελέγξουμε εάν είναι μικρότερο ή ίσο με την έξοδο , είναι αλήθεια και θα προχωρήσουμε για την προσθήκη της τιμής εξόδου και arr [i] και θα την αποθηκεύσουμε στην έξοδο και έχουμε τώρα 2 στην έξοδο. Και πάλι θα ελέγξουμε τις τιμές, αλλά τώρα οποιαδήποτε τιμή στον πίνακα δεν είναι ίση ή μικρότερη από την έξοδο, οπότε τελικά το 2 είναι η απαιτούμενη απάντηση και θα την επιστρέψουμε.

Κωδικός για να βρείτε τη μικρότερη θετική ακέραια τιμή που δεν μπορεί να αναπαρασταθεί ως άθροισμα οποιουδήποτε υποσυνόλου ενός δεδομένου πίνακα

Κωδικός C ++

#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

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

 

Ανάλυση πολυπλοκότητας

Χρόνος πολυπλοκότητας για την εύρεση της μικρότερης θετικής τιμής αριθμού που δεν υπάρχει ως άθροισμα υποσυνόλου σε πίνακα

Κάθε φορά που διασχίζουμε απλώς έναν πίνακα, κάνουμε μια λειτουργία γραμμικής πολυπλοκότητας χρόνου. Και δεδομένου ότι εδώ δεν κάνουμε τίποτα εκτός από την απλή διέλευση, έχουμε γραμμική πολυπλοκότητα χρόνου. O (n) όπου «Ν»  είναι ο αριθμός των στοιχείων στον πίνακα.

Space Complexity για την εύρεση της μικρότερης θετικής τιμής αριθμού που δεν υπάρχει ως άθροισμα υποσυνόλου σε πίνακα

Έχουμε απλώς έναν ενιαίο πίνακα που αποθηκεύει την είσοδο, έτσι ο αλγόριθμος έχει επίσης γραμμική πολυπλοκότητα χώρου. O (n) όπου «Ν»  είναι ο αριθμός των στοιχείων στον πίνακα.