નાનામાં સકારાત્મક પૂર્ણાંક મૂલ્ય શોધો કે જે આપેલા એરેના કોઈપણ સબસેટના સરવાળા તરીકે રજૂ થઈ શકશે નહીં


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે ડેટાબેક્સ ફેબ ટેક્સી 4 સ્યુર યુએચજી ઓપ્ટમ
અરે

સમસ્યા નિવેદન

તમને આપવામાં આવે છે એ સortedર્ટ થયેલ પૂર્ણાંકોનો એરે. આપણને નાનામાં સકારાત્મક પૂર્ણાંક મૂલ્ય શોધવાની જરૂર છે જે આપેલ કોઈપણ ઉપગણના રકમ તરીકે રજૂ કરી શકાતી નથી એરે.

ઉદાહરણ

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.

 

સમજૂતી

નાનામાં સકારાત્મક પૂર્ણાંક મૂલ્ય શોધો કે જે આપેલા એરેના કોઈપણ સબસેટના સરવાળા તરીકે રજૂ થઈ શકશે નહીં

 

 

અમને પૂર્ણાંકોની સortedર્ટ એરે આપવામાં આવે છે. સમસ્યાનું નિવેદન, નાનામાં સકારાત્મક પૂર્ણાંક મૂલ્ય શોધવાનું કહે છે તે આપેલ એરેના કોઈપણ સબસેટના સરવાળા તરીકે રજૂ થઈ શકશે નહીં. આપણે આ સોલ્યુશન રેખીય રીતે શોધી શકીએ સમય જટિલતા ઓ (એન) જેમ આપણી પાસે પહેલેથી જ એક એરે સ sર્ટ થયેલ છે. તેથી આપણે ક્રમમાં અથવા સંખ્યાના તફાવત વિશે ચિંતા કરવાની જરૂર નથી તેથી જ અમે આને રેખીય સમયમાં શોધી શકશું.

આપણે એરેને પસાર કરીશું. પરંતુ તે પહેલાં આઉટપુટનું મૂલ્ય 1 પર સેટ કરો, કારણ કે ઓછામાં ઓછું ત્યાં સકારાત્મક પૂર્ણાંક હશે. જો આપણી પાસે એરે 1 થી શરૂ થતું નથી, તો પછી તે આઉટપુટ વેલ્યુ તરીકે 1 પરત આવશે. તેથી આઉટપુટ વેલ્યુ 1 તરીકે સેટ કર્યા પછી, એરેને ટ્રversવર્સ કરીશું. આપણે એરેનું પ્રથમ તત્વ પસંદ કરીશું અને તપાસ કરીશું કે તે આઉટપુટના મૂલ્ય કરતા નાના છે કે બરાબર છે. જો તે સાચું છે તો આપણે આઉટપુટ અને વર્તમાન એરે એલિમેન્ટનું મૂલ્ય ઉમેરીશું. અને પછી આ આઉટપુટ પર સંગ્રહિત કરો. અમે આ કરવાનું ચાલુ રાખીશું ત્યાં સુધી એરે એલિમેન્ટનું મૂલ્ય આઉટપુટના મૂલ્યો કરતા વધારે નહીં જાય. પછી તે લૂપમાંથી બહાર આવશે અને આપણે આઉટપુટની કિંમત પાછા આપીશું.

જો આપણે અરર તરીકે ઉદાહરણ લઈએ [] = {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

 

જટિલતા વિશ્લેષણ

એરેમાં સબસેટ રકમ તરીકે અસ્તિત્વમાં ન હોય તેવા નાના હકારાત્મક સંખ્યા મૂલ્યને શોધવા માટેની સમયની જટિલતા

જ્યારે પણ આપણે સરળ રીતે કોઈ એરે પસાર કરીએ છીએ, અમે રેખીય સમય જટિલતાનું doingપરેશન કરીએ છીએ. અને કારણ કે અહીં આપણે એકલ આશ્ચર્ય સિવાય કંઇ કરી રહ્યા નથી, અમારી પાસે રેખીય સમયની જટિલતા છે. ઓ (એન) જ્યાં “એન”  એરેમાં તત્વોની સંખ્યા છે.

એરેમાં સબસેટ રકમ તરીકે અસ્તિત્વમાં ન હોય તેવા નાના હકારાત્મક સંખ્યા મૂલ્યને શોધવા માટે અવકાશ જટિલતા

આપણી પાસે ઇનપુટ સ્ટોર કરવા માટે ફક્ત એક જ એરે હોય છે, આમ તો એલ્ગોરિધમમાં પણ રેખીય અવકાશ જટિલતા હોય છે. ઓ (એન) જ્યાં “એન”  એરેમાં તત્વોની સંખ્યા છે.