রোমান থেকে ইন্টিজার লাইটকোড সলিউশন


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় রৌদ্রপক্ব ইষ্টক মর্দানী স্ত্রীলোক আপেল ব্লুমবার্গ ফেসবুক গোল্ডম্যান শ্যাস গুগল লিঙ্কডইন মাইক্রোসফট আকাশবাণী Qualtrics Roblox উবার নরপশু
ম্যাথ স্ট্রিং

"রোমান থেকে পূর্ণসংখ্যার" সমস্যায় আমাদের একটি দেওয়া হয় স্ট্রিং এর মধ্যে কিছু ইতিবাচক পূর্ণসংখ্যা উপস্থাপন করা রোমান সংখ্যা রূপ। রোমান সংখ্যাগুলি 7 টি অক্ষর দ্বারা প্রতিনিধিত্ব করা হয় যা নিম্নলিখিত টেবিলটি ব্যবহার করে পূর্ণসংখ্যায় রূপান্তর করতে পারে:

রোমান থেকে ইন্টিজার লাইটকোড সলিউশন

বিঃদ্রঃ: প্রদত্ত রোমান অঙ্কের পূর্ণসংখ্যা মান 4000 এর চেয়ে বেশি বা সমান হবে না।

উদাহরণ

IX
9
CXXIX
129

ব্যাখ্যা # 1

পূর্ণসংখ্যা 9 ম হয়

ব্যাখ্যা # 2

CXXIX = সি + XX + IX = 100 + 20 + 9 = 129

পদ্ধতির (বাম থেকে ডান দিকে)

অ্যারেতে আমরা একটি বাম থেকে ডান পাস করতে পারি এবং এতে প্রতিটি অক্ষরের জন্য সংশ্লিষ্ট মান যুক্ত রাখতে পারি। তবে, রোমান সংখ্যার অদ্ভুত দিকটি হ'ল যদি কোনও উচ্চ মানের এর আগে কম পূর্ণসংখ্যার মানের একটি অক্ষর ঘটে তবে ফলাফলটি তাদের স্বতন্ত্র যোগফল হয় না।

উদাহরণস্বরূপ, রোমানের IX এর সাথে 1 + 10 = 11 সমান হওয়া উচিত যদি আমরা পরে অক্ষর যুক্ত করি। তবে, IX = 9, হিসাবে যে আগে ঘটে X অবিচ্ছেদ্য মান কম। সুতরাং, ফলাফল হিসাবে হিসাবে চিকিত্সা করা হয় I থেকে বিয়োগ X। সুতরাং, IX = 9।

অতএব, আমরা স্ট্রিংয়ে প্রতিটি চরিত্রের পূর্ণসংখ্যার মানটি যুক্ত করতে পারি না। উপরে বর্ণিত মামলার জন্য আমাদের পাশের চরিত্রটিও পরীক্ষা করা দরকার। এইভাবে, আমরা প্রদত্ত রোমান অঙ্কের স্ট্রিংকে প্রয়োজনীয় পূর্ণসংখ্যায় রূপান্তর করতে পারি।

অ্যালগরিদম

  1. একটি ফাংশন তৈরি করুন getInteger () এটি ব্যবহার করে পাস করা একক রোমান চরিত্রের মান ফেরত দিতে সুইচ মামলা
  2. আরম্ভ ফল প্রয়োজনীয় পূর্ণসংখ্যা সঞ্চয় করতে
  3. আবার শুরু করুন বর্তমান এবং পরবর্তী প্রতিটি পুনরাবৃত্তির জন্য স্ট্রিংয়ে স্বতন্ত্র অক্ষরের বর্তমান এবং পরবর্তী সংখ্যার মান সংরক্ষণ করতে store
  4. I = 0 পর্যন্ত অবধি আইট্রেট করুন i <এন  (অ্যারের এন = আকার)
    • If i অ্যারের শেষ সূচক, আমাদের কোনও পরবর্তী অক্ষর নেই, সুতরাং এর পূর্ণসংখ্যা মান যুক্ত করুন স্ট্রিং [আমি] এবং বিনিময়ে ফল
    • ব্যবহার করে বর্তমান এবং পরবর্তী অক্ষরের পূর্ণসংখ্যা মানটি পুনরুদ্ধার করুন getInteger ()
    • If বর্তমান <= পরের
      • বিজ্ঞাপন বর্তমান থেকে ফল
      • বৃদ্ধি i 1 দ্বারা, অর্থাৎ, i++
    • আর
      • বিজ্ঞাপন পরবর্তী - বর্তমান থেকে ফল
      • বৃদ্ধি i ২ দ্বারা, অর্থাৎ, 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. স্ট্রিংয়ের শেষ অক্ষরের পূর্ণসংখ্যা মান সংরক্ষণ করুন পূর্ববর্তী
  3. আরম্ভ ফল সমান পূর্ববর্তী
  4. থেকে Iterate i = N - 2 পর্যন্ত i> = 0:
    1. বর্তমান অক্ষরের পূর্ণসংখ্যা মান হিসাবে সঞ্চয় করুন বর্তমান
    2. If বর্তমান কম পূর্ববর্তী
      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), আমরা কেবল স্থির মেমরি স্পেস ব্যবহার করি।