રોમન ટુ ઇંટીજર લીટકોડ સોલ્યુશન


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એડોબ એમેઝોન સફરજન બ્લૂમબર્ગ ફેસબુક ગોલ્ડમૅન સૅશ Google LinkedIn માઈક્રોસોફ્ટ ઓરેકલ ક્વોલિટિક્સ Roblox ઉબેર યાહૂ
મઠ શબ્દમાળા

“રોમન ટુ ઇંટીજર” સમસ્યામાં, અમને એ શબ્દમાળા તેમાં કેટલાક સકારાત્મક પૂર્ણાંકનું પ્રતિનિધિત્વ કરવું રોમન સંખ્યાત્મક સ્વરૂપ રોમન આંકડાઓ નીચેના કોષ્ટકનો ઉપયોગ કરીને પૂર્ણાંકોમાં રૂપાંતરિત કરી શકાય તેવા 7 અક્ષરો દ્વારા રજૂ થાય છે:

રોમન ટુ ઇંટીજર લીટકોડ સોલ્યુશન

નૉૅધ: આપેલ રોમન અંકનું પૂર્ણાંક મૂલ્ય 4000 કરતા વધુ અથવા તેનાથી વધુ નહીં.

ઉદાહરણ

IX
9
CXXIX
129

સમજૂતી # 1

પૂર્ણાંકોમાં IX 9 છે

સમજૂતી # 2

CXXIX = સી + XX + IX = 100 + 20 + 9 = 129

અભિગમ (ડાબેથી જમણે પાસ)

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

ઉદાહરણ તરીકે, રોમાંના નવમાં 1 + 10 = 11 બરાબર હોવું જોઈએ જો આપણે ત્યારબાદ અક્ષરો ઉમેર્યા. પરંતુ, IX = 9, જેમ કે તે પહેલાં થાય છે X અભિન્ન મૂલ્યમાં ઓછું છે. તેથી, પરિણામ તરીકે ગણવામાં આવે છે I માંથી બાદબાકી X. તેથી, નવમી = 9.

તેથી, આપણે શબ્દમાળામાં દરેક પાત્રનું પૂર્ણાંક મૂલ્ય ઉમેરી શકતા નથી. ઉપરોક્ત કેસમાં આપણે તેની પાસેના પાત્રને પણ તપાસવાની જરૂર છે. આ રીતે, અમે આપેલ રોમન આંકડાને જરૂરી પૂર્ણાંકમાં રૂપાંતરિત કરી શકીએ છીએ.

અલ્ગોરિધમ

  1. ફંકશન બનાવો getInteger () એક રોમન પાત્રની કિંમત વાપરીને પરત કરવા માટે સ્વીચ કિસ્સાઓ
  2. પ્રારંભ કરો પરિણામ જરૂરી પૂર્ણાંક સંગ્રહવા માટે
  3. ફરીથી, પ્રારંભ કરો વર્તમાન અને આગામી પ્રત્યેક પુનરાવૃત્તિ માટે શબ્દમાળામાં સંબંધિત અક્ષરોના વર્તમાન અને આગામી પૂર્ણાંક મૂલ્યોનું મૂલ્ય સંગ્રહવા
  4. I = 0 સુધીનું ઇટેરેટ કરો i <એન  (એન = એરેનું કદ)
    • If i એરેનું છેલ્લું અનુક્રમણિકા છે, અમારી પાસે આગળનું પાત્ર નથી, તેથી તેનું પૂર્ણાંક મૂલ્ય ઉમેરો શબ્દમાળા [i] અને પાછા પરિણામ
    • ઉપયોગ કરીને વર્તમાન અને આગળના અક્ષરોનું પૂર્ણાંક મૂલ્ય પ્રાપ્ત કરો getInteger ()
    • If વર્તમાન <= આગળ
      • ઉમેરવું વર્તમાન માટે પરિણામ
      • વધારો i 1 દ્વારા, એટલે કે, i++
    • બીજું
      • ઉમેરવું આગામી - વર્તમાન માટે પરિણામ
      • વધારો i 2 દ્વારા, એટલે કે, i + = 2
  5. પરિણામ છાપો

રોમન ટુ ઇંટીજર લેટકોડ સોલ્યુશનનો અમલ

સી ++ પ્રોગ્રામ

#include <bits/stdc++.h>
using namespace std;

int getInteger(char c)
{
    switch(c)
    {
        case 'I' : return 1;
        case 'V' : return 5;
        case 'X' : return 10;
        case 'L' : return 50;
        case 'C' : return 100;
        case 'D' : return 500;
        case 'M' : return 1000;
        default : return -1;
    }
}

int romanToInt(string s)
{
    int n = s.size() , result = 0 , current , next , i = 0;
    while(i < n)
    {
        if(i == n - 1)
        {
            result += getInteger(s[i]);
            return result;
        }
        current = getInteger(s[i]) , next = getInteger(s[i + 1]);
        if(current >= next)
            result += current , i++;
        else
            result += next - current , i += 2;
    }
    return result;
}

int main()
{
    string s = "CXXIX";
    cout << romanToInt(s) << '\n';
    return 0;
}

જાવા પ્રોગ્રામ

class roman_to_int
{
    public static void main(String args[])
    {
        String s = "CXXIX";
        System.out.println(romanToInt(s));
    }

    static int getInteger(char c)
    {
        switch(c)
        {
            case 'I' : return 1;
            case 'V' : return 5;
            case 'X' : return 10;
            case 'L' : return 50;
            case 'C' : return 100;
            case 'D' : return 500;
            case 'M' : return 1000;
            default : return -1;
        }
    }

    static int romanToInt(String s)
    {
        int n = s.length() , result = 0 , current , next , i = 0;
        while(i < n)
        {
            if(i == n - 1)
            {
                result += getInteger(s.charAt(i));
                return result;
            }
            current = getInteger(s.charAt(i));
            next = getInteger(s.charAt(i + 1));
            if(current >= next)
            {
                result += current;
                i++;
            }
            else
            {
                result += next - current;
                i += 2;
            }
        }
        return result;
    }
}
129

રોમનથી પૂર્ણાંક લેટકોડ સોલ્યુશનનું જટિલતા વિશ્લેષણ

સમય જટિલતા

અહીં, અમે એકવાર શબ્દમાળાને વટાવીએ છીએ. આપણી પાસે પૂર્ણાંક 4000 કરતા ઓછી મર્યાદા હોવાથી, શબ્દમાળાના કદ હંમેશા સ્થિર મૂલ્ય રહેશે. તેથી, સમય જટિલતા છે ઓ (1).

જગ્યાની જટિલતા

ઓ (1), અમે ફક્ત સતત મેમરી સ્પેસનો ઉપયોગ કરીએ છીએ.

અભિગમ (જમણેથી ડાબે પાસ)

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

આ અભિગમ લગભગ અગાઉના અભિગમની જેમ કામગીરીની સંખ્યામાં સમાન છે પરંતુ વધુ અનુકૂળ છે કારણ કે આપણે દરેક પુનરાવૃત્તિ માટે છેલ્લા ઘટકની તપાસ કરવામાં છૂટકારો મેળવીએ છીએ.

અલ્ગોરિધમ

  1. ફંકશન બનાવો getInteger () ઉપરની જેમ જ
  2. માં શબ્દમાળાના છેલ્લા પાત્રનું પૂર્ણાંક મૂલ્ય સ્ટોર કરો prev
  3. પ્રારંભ કરો પરિણામ સમાન prev
  4. માંથી Iterate i = N - 2 ત્યાં સુધી i> = 0:
    1. વર્તમાન પાત્રનું પૂર્ણાંક મૂલ્ય સ્ટોર કરો વર્તમાન
    2. If વર્તમાન કરતાં ઓછું છે prev
      1. બાદબાકી વર્તમાન થી પરિણામ, તે જ, પરિણામ -= વર્તમાન
    3. બીજું
      1. ઉમેરવું વર્તમાન થી પરિણામ, તે જ, પરિણામ += વર્તમાન
  5. પરિણામ છાપો

રોમન ટુ ઇંટીજર લેટકોડ સોલ્યુશનનો અમલ

સી ++ પ્રોગ્રામ

#include <bits/stdc++.h>
using namespace std;

int getInteger(char c)
{
    switch(c)
    {
        case 'I' : return 1;
        case 'V' : return 5;
        case 'X' : return 10;
        case 'L' : return 50;
        case 'C' : return 100;
        case 'D' : return 500;
        case 'M' : return 1000;
        default : return -1;
    }
}

int romanToInt(string s)
{
    int n = s.size();
    int prev = getInteger(s[n - 1]) , result = prev , current;
    for(int i = n - 2 ; i >= 0 ; i--)
    {
        current = getInteger(s[i]);
        if(current < prev)
            result -= current;
        else
            result += current;
        prev = current;
    }
    return result;
}

int main()
{
    string s = "CXXIX";
    cout << romanToInt(s) << '\n';
    return 0;
}

જાવા પ્રોગ્રામ

class roman_to_int
{
    public static void main(String args[])
    {
        String s = "CXXIX";
        System.out.println(romanToInt(s));
    }

    static int getInteger(char c)
    {
        switch(c)
        {
            case 'I' : return 1;
            case 'V' : return 5;
            case 'X' : return 10;
            case 'L' : return 50;
            case 'C' : return 100;
            case 'D' : return 500;
            case 'M' : return 1000;
            default : return -1;
        }
    }

    static int romanToInt(String s)
    {
        int n = s.length();
        int prev = getInteger(s.charAt(n - 1)) , result = prev , current;
        for(int i = n - 2 ; i >= 0 ; i--)
        {
            current = getInteger(s.charAt(i));
            if(current < prev)
                result -= current;
            else
                result += current;
            prev = current;
        }
        return result;
    }
}
129

રોમનથી પૂર્ણાંક લેટકોડ સોલ્યુશનનું જટિલતા વિશ્લેષણ

સમય જટિલતા

ફરીથી, અમે એકવાર શબ્દમાળાને વટાવીએ છીએ. ઉપર ચર્ચા મુજબ, સમયની જટિલતા છે ઓ (1).

જગ્યાની જટિલતા

ઓ (1), અમે ફક્ત સતત મેમરી સ્પેસનો ઉપયોગ કરીએ છીએ.