આપેલ ક્રમથી ન્યૂનતમ સંખ્યા બનાવો


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે ભેગા એમેઝોન કટ્ટરતા ગોલ્ડમૅન સૅશ માહિતી એજ Snapchat
અરે સ્ટેક શબ્દમાળા

સમસ્યા "આપેલ ક્રમમાંથી ન્યૂનતમ સંખ્યા બનાવો" જણાવે છે કે તમને કેટલીક પેટર્ન આપવામાં આવી છે હું અને ડી માત્ર. નો અર્થ I એટલે કે વધતી જતી અને ઓછી થવાની આપણને પૂરી પાડવામાં આવે છે D. સમસ્યાનું નિવેદન લઘુતમ સંખ્યાને છાપવાનું કહે છે જે આપેલ પેટર્નને સંતોષે છે. આપણે 1-9 ના અંકોનો ઉપયોગ કરવો પડશે અને કોઈ અંકનું પુનરાવર્તન થવું જોઈએ નહીં.

ઉદાહરણ

DIID
21354

સમજૂતી

પ્રથમ અંક 2 છે પછી તેને ઘટાડ્યા પછીનો અંક 1 હશે. પછી 2 નો વધારો 3 કરશે જે લઘુત્તમ અંકો જે 2 કરતા વધારે છે અને અને પછી આપણે તેને ફરીથી વધારવો પડશે પરંતુ ફરી વધારો કર્યા પછી, આપણે તેને ઘટાડવો પડશે . કારણ કે અંકો પુનરાવર્તિત કરી શકાતા નથી. તેથી આપણે તેને 2 દ્વારા વધારીશું અને પછી તેને 1 દ્વારા ઘટાડીશું.

તેથી આઉટપુટ 2 1 3 5 4 બનશે

ફરીથી આપણે વર્તમાન અંકો વધારીએ છીએ. પરંતુ તે કરવાથી અમને 4 મળશે અને તે ઘટ્યા પછી આપણે ક્યાં તો 1, 2, અથવા 3 નો ઉપયોગ કરવો પડશે અને આ બધા અંકો પહેલાથી જ ઉપયોગમાં લેવામાં આવ્યા હતા. તેથી આપણે વર્તમાન અંક વધારીને 5 કરવાની જરૂર છે. અને તે જ રીતે આપણે જવાબ સુધી પહોંચીએ છીએ.

આપેલ ક્રમથી ન્યૂનતમ સંખ્યા રચવા માટે અલ્ગોરિધમનો

  1. આપેલ ક્રમ લંબાઈ 9 કરતા વધારે અથવા બરાબર છે કે નહીં તે તપાસો, જો સાચું હોય તો -1 પરત ફરો.
  2. કદ n + 1 ના કદની ચાર એરે જાહેર કરો અને ગણતરીનું મૂલ્ય 1 પર સેટ કરો.
  3. 0 થી એન (સમાવિષ્ટ) થી એરેને ટ્રversવર્સ કરવાનું પ્રારંભ કરો.
    1. જો તપાસો i ની બરાબર છે n અથવા શબ્દમાળાનું વર્તમાન પાત્ર "I" ની બરાબર છે, જો તે પછી સાચું હોય
      1. -1 ના પહેલાના મૂલ્યથી એરેને વટાવી દો.
        1. નીચેના પગલાંઓ કરીને આઉટપુટ એરેના મૂલ્યોને અપડેટ કરો.
          1. ગણતરીના મૂલ્યમાં વધારો અને તેને આઉટપુટ એરેમાં સંગ્રહિત કરો.
          2. જો તપાસો j વર્તમાન અનુક્રમણિકા 0 કરતા વધારે છે, અને શબ્દમાળાઓનું વર્તમાન પાત્ર પણ “I” છે, પછી, વિરામ.
  4. રીટર્ન પરિણામ.

સમજૂતી

ફક્ત એક શબ્દમાળા આપવામાં આવે છે અને હું અને ડીનો જ, અમને તે પેટર્નને છાપવાનું કહેવામાં આવે છે જે આપેલ સાથે રચાય છે શબ્દમાળા. અહીં I તે વધતા જતાનો ઉલ્લેખ કરે છે કે આપણને આપેલ ક્રમને ન્યાયી ઠેરવી શકે તે ન્યૂનતમ સંખ્યા બનાવવી અથવા બનાવવી પડશે. ધારો કે જો આપણે કહીએ DIજ્યાં D એટલે કે લઘુત્તમ સંખ્યામાં ઘટાડો થવાનો અર્થ એ છે કે ન્યુનત્તમ સંખ્યા તરીકે 2 ની રચના પછી 21 આવે છે. અંકો પુનરાવર્તિત કરી શકાતા નથી, સંખ્યામાં ફક્ત 1-9 ના અંકો હોઈ શકે છે. તે પછી, "હું" ત્યાં છે, આપણે ન્યૂનતમ વધતી સંખ્યા બનાવવી જોઈએ. 21 પહેલાથી જ ત્યાં છે. અમારું લક્ષ્ય છે કે આપણે વધતી જતી સંખ્યા બનાવવી. આ રીતે 1 પછી 3 આવે છે, કારણ કે 2 પહેલાથી ઉપયોગમાં છે, અને તે પછી 3 એ એકમાત્ર સંખ્યા છે જે જોડાઈ શકે છે.

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

ઇનપુટ તરીકે અમને પ્રાપ્ત થયેલ શબ્દમાળાને વટાવી દો. જો વર્તમાન અનુક્રમણિકા શબ્દમાળાની લંબાઈ જેટલી છે અથવા વર્તમાન પાત્ર "I" ની બરાબર છે. પછી ફક્ત આપણે આગળ વધીએ. તે પછી, વર્તમાન મૂલ્ય (i) ની પહેલાની કિંમતથી, -1 સુધી પહોંચવાની શરૂઆત કરો. આ લૂપની અંદર આપણે ઈન્ડેક્સ j + 1 પર આઉટપુટ એરેમાં ગણતરીના મૂલ્યમાં વધારો અને સ્ટોર કરવાનું ચાલુ રાખીએ છીએ. પછી તેનું મૂલ્ય તપાસો j કરતા વધારે અથવા બરાબર છે 0 અને જો વર્તમાન પાત્ર "હું" છે. જો સાચું હોય, તો પછી લૂપને તોડી નાખો અને વધુ પાત્રો માટે આગળ વધો.

કોડ

આપેલ ક્રમથી ન્યૂનતમ સંખ્યા બનાવવા માટે સી ++ કોડ

#include<iostream>

using namespace std;

string getMinimumNumberSeq(string str)
{
    int n = str.length();

    if (n >= 9)
        return "-1";

    string output(n+1, ' ');

    int count = 1;

    for (int i = 0; i <= n; i++)
    {
        if (i == n || str[i] == 'I')
        {
            for (int j = i - 1 ; j >= -1 ; j--)
            {
                output[j + 1] = '0' + count++;
                if(j >= 0 && str[j] == 'I')
                    break;
            }
        }
    }
    return output;
}
int main()
{
    string inputs[] = { "DIID", "ID", "II", "DI", "DDII", "IDID", "IDIDID"};

    for (string input : inputs)
    {
        cout << getMinimumNumberSeq(input) << "\n";
    }
    return 0;
}
21354
132
123
213
32145
13254
1325476

આપેલ ક્રમથી ન્યૂનતમ સંખ્યા બનાવવાનો જાવા કોડ

class minimumNumberID
{
    static String getMinimumNumberSeq(String str)
    {
        int n = str.length();

        if (n >= 9)
            return "-1";

        char output[] = new char[n + 1];

        int count = 1;

        for (int i = 0; i <= n; i++)
        {
            if (i == n || str.charAt(i) == 'I')
            {
                for (int j = i - 1; j >= -1; j--)
                {
                    output[j + 1] = (char) ((int) '0' + count++);
                    if (j >= 0 && str.charAt(j) == 'I')
                        break;
                }
            }
        }
        return new String(output);
    }
    public static void main(String[] args)
    {
        String inputs[] = { "DIID", "ID", "II", "DI", "DDII", "IDID", "IDIDID" };

        for(String input : inputs)
        {
            System.out.println(getMinimumNumberSeq(input));
        }
    }
}
21354
132
123
213
32145
13254
1325476

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

સમય જટિલતા

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

અવકાશ જટિલતા

ઓ (એન), કારણ કે આપણે પરિણામ સંગ્રહવા માટે આઉટપુટ કેરેક્ટર એરે બનાવ્યો છે. સમસ્યા માટેની જગ્યા જટિલતા પણ રેખીય છે.