రోమన్ లీట్‌కోడ్ సొల్యూషన్‌కు పూర్ణాంకం  


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది Adobe అమెజాన్ ఆపిల్ నలుపు రాయి బ్లూమ్బెర్గ్ Evernote <span style="font-family: Mandali; ">ఫేస్‌బుక్ </span> గూగుల్ లింక్డ్ఇన్ మైక్రోసాఫ్ట్ ఒరాకిల్ <span style="font-family: Mandali; ">ట్విట్టర్</span> యాహూ
అల్గోరిథంలు కోడింగ్ ఇంటర్వ్యూ ఇంటర్వ్యూ ప్రిపరేషన్ లీట్‌కోడ్ LeetCodeSolutions మఠం స్ట్రింగ్

ఈ సమస్యలో, మాకు పూర్ణాంకం ఇవ్వబడుతుంది మరియు రోమన్ సంఖ్యలుగా మార్చాల్సిన అవసరం ఉంది. అందువల్ల సమస్యను సాధారణంగా "ఇంటీజర్ టు రోమన్" అని పిలుస్తారు మరియు ఇది రోమన్ లీట్‌కోడ్ సొల్యూషన్‌కు పూర్ణాంకం. రోమన్ సంఖ్యల గురించి ఎవరికైనా తెలియకపోతే. పాత కాలంలో, ఇటీవలి కాలంలో మనం ఉపయోగించినట్లు ప్రజలు పూర్ణాంకాలను ఉపయోగించలేదు.

రోమన్ సంఖ్యలు సాధారణంగా ఎడమ నుండి కుడికి తగ్గుతున్న క్రమంలో వ్రాయబడతాయి, అయితే దీనికి కొన్ని మినహాయింపులు ఉన్నాయి. తరువాతి సంఖ్య కంటే చిన్నదైన కొన్ని సంఖ్యలు ఉంటే, ప్రస్తుత సంఖ్యను సానుకూల మొత్తం నుండి తీసివేస్తాము. బొటనవేలు యొక్క సాధారణ నియమం ఒకే సంఖ్యను 3 కన్నా ఎక్కువసార్లు పునరావృతం చేయకూడదు. రోమన్ సంఖ్యా మార్పిడికి పూర్ణాంకం కోసం ఈ క్రింది చిత్రాన్ని తనిఖీ చేయాలి.

రోమన్ లీట్‌కోడ్ సొల్యూషన్‌కు పూర్ణాంకంపిన్

3
III

వివరణ: నేను 1 కి సమానం కాబట్టి, మొత్తం = 3 పొందడానికి మూడుసార్లు పునరావృతం చేస్తాము.

4
IV

వివరణ: మేము I ను 4 సార్లు పునరావృతం చేయలేము, ఎందుకంటే మనం 3 సార్లు కంటే ఎక్కువ పునరావృతం చేయలేము. కాబట్టి మనం V కి ముందు I ని విమానం చేస్తాను. నేను V కన్నా తక్కువ కాబట్టి, 1 మొత్తం 5 నుండి సమానంగా ఉంటుంది. కాబట్టి మొత్తం మొత్తాన్ని 4 కి సమానంగా చేస్తుంది.

రోమన్ లీట్‌కోడ్ సొల్యూషన్‌కు పూర్ణాంకం కోసం విధానం  

“ఇంటీజర్ టు రోమన్” అనే సమస్యను అత్యాశతో పరిష్కరించవచ్చు, మొదట మనం సంఖ్యను సాధ్యమైనంత ఎక్కువ సంఖ్యగా మార్చడానికి ప్రయత్నిస్తాము. సమస్యకు బ్రూట్ ఫోర్స్ విధానం సాధ్యం కాదు ఎందుకంటే ఇది సాధ్యమయ్యేది కాదు లేదా సాధారణంగా వర్తించదు. ఈ పద్ధతిలో మేము రోమన్ సంఖ్యాలో చిన్న తెగలకి వెళ్తాము. మేము 4 ని మార్చడానికి ప్రయత్నించినప్పుడు ఈ విధానం విఫలమవుతుంది. ఈ విధానం 4 సార్లు I ని ప్రింట్ చేస్తుంది. కాబట్టి, దీని చుట్టూ తిరగడానికి మనం ఒక మార్గాన్ని కనుగొనాలి.

ఇది కూడ చూడు
ఒక సంఖ్యను హెక్సాడెసిమల్ లీట్‌కోడ్ సొల్యూషన్‌గా మార్చండి

సరే, మనం నిశితంగా పరిశీలిస్తే, ఈ మినహాయింపులో మనం పరిగెత్తగలిగే కొన్ని మార్గాలు మాత్రమే ఉన్నాయి. ఈ మినహాయింపు మేము కొన్ని సంఖ్యలను 3 సార్లు కంటే ఎక్కువ పునరావృతం చేసినప్పుడు మాత్రమే. కాబట్టి మినహాయింపులో పడే పూర్ణాంకాలను వ్రాయడానికి మార్గాలను కనుగొనడానికి ప్రయత్నించండి. మినహాయింపు 4, 9, 40, 90, 400, 900 అని తెలుసుకుంటాము, వీటిని వరుసగా IV, IX, XL, XC, CD, CM గా మార్చవచ్చు.

మినహాయింపులతో వ్యవహరించడం

కాబట్టి, ఇప్పటి వరకు మేము ఇచ్చిన పూర్ణాంకాన్ని అందుబాటులో ఉన్న అసలు సింగిల్ క్యారెక్టర్ రోమన్ సంఖ్యలకు మార్చాలని ఆలోచిస్తున్నాము. కానీ మినహాయింపు నుండి బయటపడటానికి, మేము వాటిని విడిగా నిర్వహిస్తాము. ఈ విధంగా, మేము రెండు సృష్టిస్తాము శ్రేణుల ప్రతి రోమన్ సంఖ్యకు అనుగుణమైన సమగ్ర విలువను నిల్వ చేస్తుంది. ఇతర శ్రేణి రోమన్ సంఖ్యలను నిల్వ చేస్తుంది. ఈ రెండు శ్రేణులు పూర్ణాంకాలు మరియు రోమన్ సంఖ్యలను ఒకే సంబంధిత సూచికలలో నిల్వ చేస్తాయి.

ఇప్పుడు, మనకు మిగిలింది కేవలం అత్యాశతో చేసిన మార్పిడిని ఉపయోగించడం. అతిపెద్ద రోమన్ సంఖ్యతో ప్రారంభించండి మరియు ప్రస్తుత రోమన్ సంఖ్యా సమానమైన సంఖ్య కంటే ఎక్కువ ఉంటే. రోమన్ సంఖ్యను సమాధానంగా చేర్చండి స్ట్రింగ్ మరియు ఇచ్చిన పూర్ణాంకం నుండి సమగ్ర విలువను తీసివేయండి. ఇచ్చిన పూర్ణాంకం ప్రస్తుత సంఖ్య కంటే ఎక్కువగా ఉండే వరకు ప్రస్తుత సంఖ్యను తీసివేయండి. ప్రస్తుత సంఖ్య ప్రస్తుత పూర్ణాంక విలువ కంటే తక్కువగా ఉన్నప్పుడు మీరు ఒక దశకు చేరుకున్న తర్వాత. తదుపరి చిన్న రోమన్ సంఖ్య కోసం తనిఖీ చేయండి. మేము అన్ని రోమన్ సంఖ్యలతో పూర్తి చేసిన తర్వాత, మేము సమాధానం ఇస్తాము.

రోమన్ లీట్‌కోడ్ సొల్యూషన్‌కు పూర్ణాంకం కోసం కోడ్  

ఇంటీజర్ టు రోమన్ లీట్‌కోడ్ సొల్యూషన్ కోసం సి ++ కోడ్

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

string intToRoman(int num) {
    vector<string> romans({"I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M"});
    vector<int> value({1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000});
    int seqSize = romans.size();
    int idx = seqSize - 1;
    string ans = "";
    while(num>0){
        while(value[idx]<=num){
            ans += romans[idx];
            num -= value[idx];
        }
        idx--;
    }
    return ans;
}

int main(){
    cout<<intToRoman(4);
}
IV

రోమన్ లీట్‌కోడ్ సొల్యూషన్‌కు పూర్ణాంకం కోసం జావా కోడ్

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static String intToRoman(int num) {
        String romans[] = {"I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M"};
        int value[] = {1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000};
        int seqSize = romans.length;
        int idx = seqSize - 1;
        String ans = "";
        while(num>0){
            while(value[idx]<=num){
                ans += romans[idx];
                num -= value[idx];
            }
            idx--;
        }
        return ans;
    }
    public static void main(String[] args){
    	System.out.println(intToRoman(4));
    }
}

 

IV

సంక్లిష్టత విశ్లేషణ  

సమయం సంక్లిష్టత

ఓ (1), ఎందుకంటే ఫలితాన్ని కనుగొనడానికి మేము స్థిరమైన దశలను ఉపయోగిస్తున్నాము.

ఇది కూడ చూడు
సాపేక్ష క్రమబద్ధీకరణ అర్రే లీట్‌కోడ్ పరిష్కారం

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

ఓ (1), మేము స్థిరమైన వేరియబుల్స్ సంఖ్యను మాత్రమే నిల్వ చేసినందున మరియు మనం ఉపయోగించిన శ్రేణులకి కూడా స్థిరమైన పరిమాణం ఉంటుంది.