ከተሰጠው ድርድር ማናቸውም ንዑስ ድምር ሊወከል የማይችል አነስተኛውን አዎንታዊ ኢንቲጀር እሴት ያግኙ


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ የመረጃ ቋቶች Fab ታክሲ 4 ዋስትና 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.

 

ማስረጃ

ከተሰጠው ድርድር ማናቸውም ንዑስ ድምር ሊወከል የማይችል አነስተኛውን አዎንታዊ ኢንቲጀር እሴት ያግኙ

 

 

የተደረደሩ ብዛት ያላቸው ቁጥሮች ይሰጡናል። የችግሩ መግለጫ አነስተኛውን አዎንታዊ ኢንቲጀር እሴት ለማግኘት ይጠይቃል። ያ የአንድ የተወሰነ ድርድር ማናቸውም ንዑስ ድምር ሆኖ ሊወከል አይችልም። ይህንን መፍትሔ መስመራዊ በሆነ መንገድ ማግኘት እንችላለን የጊዜ ውስብስብነት ኦ (n) አንድ ድርድር እንዳለን ቀድሞውኑ ተደርድሯል። ስለዚህ በትእዛዙ ወይም በቁጥር ልዩነቶች መጨነቅ አያስፈልገንም ለዚህ ነው በመስመር ላይ ይህንን ለማግኘት የምንችለው ፡፡

ድርድርን እናቋርጣለን። ግን ከዚያ በፊት የውጤት እሴቱን ወደ 1 ያቀናብሩ ፣ ቢያንስ ቢያንስ አነስተኛ አዎንታዊ ኢንቲጀር ይሆናል ፡፡ ከ 1 ጀምሮ ድርድር ከሌለን በቀላል 1 እንደ የውጤት እሴት ይመለሳል። ስለዚህ የውጤት እሴቱን እንደ 1 ካቀናበሩ በኋላ ድርድርን በማቋረጥ ላይ። የሰልፉን የመጀመሪያውን ንጥረ ነገር እናነሳለን እና ከውጤቱ እሴት ያነሰ ወይም እኩል መሆኑን እንፈትሻለን። እውነት ከሆነ ከዚያ የውጤት እና የአሁኑን የድርድር ንጥረ ነገር ዋጋ እንጨምራለን። እና ከዚያ ይህንን ለማውጣት ያከማቹ። የአንድ ድርድር አባል እሴት ከምርት እሴቶች የማይበልጥ እስከሆነ ድረስ ይህን ማድረጋችንን እንቀጥላለን። ከዚያ ከሉፉ ይወጣል እና የውጤቱን ዋጋ እንመልሳለን።

ምሳሌ እንደ arr [] = {1,4,7,8,10} የምንወስድ ከሆነ በውጤቱ = 1 እንጀምራለን ፣ የመጀመሪያውን ንጥረ ነገር ማንሳት እንቀጥላለን እና ከምርቱ ያነሰ ወይም እኩል መሆኑን እንፈትሻለን ፣ እውነት ነው እናም የውጤት እና የአር [i] እሴትን በመደመር እንሄዳለን እና ወደ ምርቱ እናከማቸዋለን እናም አሁን በውጤቱ 2 አለን እንደገና እሴቶቹን እንፈትሻለን አሁን ግን በምድቡ ውስጥ ያለው ማንኛውም እሴት ከውጤቱ እኩል ወይም ያነሰ አይደለም ፣ ስለሆነም በመጨረሻ 2 ተፈላጊው መልሳችን ነው እናም እኛ እንመልሰዋለን ፡፡

በተጠቀሰው ድርድር ማናቸውም ንዑስ ክፍል ድምር ሊወከል የማይችል አነስተኛውን አዎንታዊ ኢንቲጀር እሴት ለማግኘት ኮድ

ሲ ++ ኮድ

#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

 

የጃቫ ኮድ

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

 

ውስብስብነት ትንተና

በቅደም ተከተል እንደ ንዑስ ድምር የማይኖር አነስተኛውን አዎንታዊ የቁጥር እሴት ለማግኘት የጊዜ ውስብስብነት

አንድን ድርድር በቀላሉ በምናቋርጥበት ጊዜ ሁሉ ፣ የመስመር ጊዜ ውስብስብነትን የምናከናውንበት ሥራ እየሠራን ነው ፡፡ እናም እዚህ እኛ ከአንድ ተሻጋሪነት ውጭ ምንም ነገር ስለማናደርግ ፣ የመስመር ጊዜ ውስብስብነት አለብን ፡፡ ሆይ (n) የት “N”  በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው።

በቅደም ተከተል እንደ ንዑስ ድምር የማይኖር አነስተኛውን አዎንታዊ የቁጥር እሴት ለማግኘት የቦታ ውስብስብነት

እኛ ግቤቱን በማከማቸት አንድ ነጠላ ድርድር አለን ፣ ስለሆነም አልጎሪዝም እንዲሁ ቀጥተኛ የቦታ ውስብስብነት አለው። ሆይ (n) የት “N”  በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው።