ఇచ్చిన క్రమం నుండి కనీస సంఖ్యను రూపొందించండి


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది అకోలైట్ అమెజాన్ ఇష్టపడేవారిని గోల్డ్మన్ సాచ్స్ సమాచారం ఎడ్జ్ 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 నుండి n వరకు ప్రయాణించడం ప్రారంభించండి (కలుపుకొని).
    1. తనిఖీ చేయండి i కు సమానం n లేదా స్ట్రింగ్ యొక్క ప్రస్తుత అక్షరం “నేను” కి సమానం, అప్పుడు నిజమైతే
      1. మునుపటి విలువ నుండి -1 వరకు శ్రేణిని దాటండి.
        1. కింది దశలను చేయడం ద్వారా అవుట్పుట్ శ్రేణి యొక్క విలువలను నవీకరించండి.
          1. గణన విలువను పెంచండి మరియు దాన్ని అవుట్పుట్ శ్రేణికి నిల్వ చేయండి.
          2. తనిఖీ చేయండి j ప్రస్తుత సూచిక 0 కన్నా ఎక్కువ, మరియు స్ట్రింగ్ యొక్క ప్రస్తుత అక్షరం “I”, అప్పుడు, విచ్ఛిన్నం.
  4. రిటర్న్ ఫలితం.

వివరణ

ఒక స్ట్రింగ్ మరియు నేను మరియు D యొక్క మాత్రమే ఇచ్చినట్లయితే, ఇచ్చిన దానితో ఏర్పడే నమూనాను ముద్రించమని అడుగుతారు స్ట్రింగ్. ఇక్కడ I పెరుగుతున్న క్రమాన్ని సమర్థించే కనీస సంఖ్యను మనం తయారు చేయాలి లేదా ఏర్పరచాలి. మనం చెబితే అనుకుందాం DI, ఎక్కడ D కనిష్ట సంఖ్యను తగ్గించడం అంటే 2 తరువాత కనిష్ట సంఖ్యగా 21 ను ఏర్పరుస్తుంది. అంకెలు పునరావృతం కావు, సంఖ్య 1-9 నుండి అంకెలను మాత్రమే కలిగి ఉంటుంది. ఆ తరువాత, “నేను” ఉంది, మనం కనీస పెరుగుతున్న సంఖ్యను ఏర్పరచాలి. 21 ఇప్పటికే ఉంది కాబట్టి. మేము పెరుగుతున్న సంఖ్యను రూపొందించాలని లక్ష్యంగా పెట్టుకున్నాము. ఈ విధంగా 1 ను 3 అనుసరిస్తుంది, ఎందుకంటే 2 ఇప్పటికే వాడుకలో ఉంది, మరియు ఆ తరువాత 3 మాత్రమే చేరగల సంఖ్య.

ఈ అన్ని భావనలు మరియు ఆలోచనలతో, ఇచ్చిన షరతులను అనుసరించే మరియు సంతృప్తిపరిచే కనీస సంఖ్యను ముద్రించమని అడుగుతారు. మేము అవుట్పుట్ శ్రేణిని ఉపయోగించబోతున్నాము, దీనిలో మన అవుట్పుట్ను ఆ అక్షర శ్రేణికి నిల్వ చేస్తాము. డేటా ధ్రువీకరణ మరియు ధృవీకరణ కోసం మేము కొన్ని షరతులను చేసాము. మేము స్ట్రింగ్ యొక్క పొడవు 9 కంటే ఎక్కువ లేదా సమానంగా కనుగొంటే, అప్పుడు మేము -1 ను తిరిగి ఇస్తాము ఎందుకంటే 1-9 అంకెలను ఉపయోగించమని మేము ఖచ్చితంగా ఆదేశించాము మరియు అంకెలు పునరావృతం కావు.

మేము ఇన్‌పుట్‌గా స్వీకరించిన స్ట్రింగ్‌ను దాటండి. ప్రస్తుత సూచిక స్ట్రింగ్ యొక్క పొడవుకు సమానంగా ఉంటే లేదా ప్రస్తుత అక్షరం “I” కి సమానం. అప్పుడు మాత్రమే మేము మరింత ముందుకు వెళ్తాము. ఆ తరువాత ప్రస్తుత విలువ (i) కి మునుపటి విలువ నుండి -1 చేరుకునే వరకు ప్రయాణించడం ప్రారంభించండి. ఈ లూప్ లోపల మేము గణన విలువను పెంచుతూ మరియు ఇండెక్స్ j + 1 వద్ద అవుట్పుట్ శ్రేణిలో నిల్వ చేస్తూనే ఉంటాము. యొక్క విలువ ఉందో లేదో తనిఖీ చేయండి j కంటే ఎక్కువ లేదా సమానం 0 మరియు ప్రస్తుత పాత్ర “నేను” అయితే. నిజమైతే, లూప్‌ను విచ్ఛిన్నం చేసి, మరిన్ని అక్షరాల కోసం ముందుకు సాగండి.

కోడ్

ఇచ్చిన క్రమం నుండి కనీస సంఖ్యను రూపొందించడానికి C ++ కోడ్

#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 నిల్వ చేసిన సూచికలపై పనిచేసేటప్పుడు మేము సమూహ లూప్‌లోకి ప్రవేశిస్తాము. ప్రతి సూచిక I లేదా D ను కలిగి ఉంటుంది కాబట్టి, మేము ప్రతి అక్షరం మీద ఒకటి మాత్రమే ప్రయాణిస్తున్నాము. అందువలన సమయం సంక్లిష్టత సరళంగా ఉంటుంది.

అంతరిక్ష సంక్లిష్టత

పై), ఎందుకంటే ఫలితాన్ని నిల్వ చేయడానికి మేము అవుట్పుట్ అక్షర శ్రేణిని సృష్టించాము. సమస్యకు స్థలం సంక్లిష్టత కూడా సరళంగా ఉంటుంది.