রোমান লেটকোড সমাধানের পূর্ণসংখ্যা


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

এই সমস্যায়, আমাদের একটি পূর্ণসংখ্যা দেওয়া হয় এবং রোমান সংখ্যায় রূপান্তর করা প্রয়োজন। সুতরাং সমস্যাটিকে সাধারণত "রোমানের ইন্টিজার" হিসাবে চিহ্নিত করা হয় এবং এটি রোমান লেটকোড সলিউশন থেকে পূর্ণসংখ্যা হয়। রোমান সংখ্যা সম্পর্কে কেউ না জানলে does পুরানো সময়ে, মানুষ সাম্প্রতিক সময়ে আমরা যেমন ব্যবহার করি না তেমন পূর্ণসংখ্যা ব্যবহার করে না।

ক্রমহ্রাসমান ক্রমে রোমান সংখ্যাগুলি বাম থেকে ডানে রচনা করা হয় তবে এর ব্যতিক্রম কিছু আছে। যদি পরবর্তী অঙ্কগুলির চেয়ে ছোট কিছু সংখ্যাসূচক হয় তবে আমরা বর্তমান সংখ্যাকে ধনাত্মক যোগ থেকে বিয়োগ করব। থাম্বের একটি সাধারণ নিয়ম একই সংখ্যাকে 3 বারের বেশি পুনরাবৃত্তি না করে। পূর্ণসংখ্যার রোমান অঙ্কের রূপান্তরকরণের জন্য নীচের চিত্রটি পরীক্ষা করা উচিত।

রোমান লেটকোড সমাধানের পূর্ণসংখ্যা

3
III

ব্যাখ্যা: যেহেতু আমি 1 এর সমতুল্য তাই আমরা যোগফল = 3 পাওয়ার জন্য এটি তিনবার পুনরাবৃত্তি করি।

4
IV

ব্যাখ্যা: আমরা 4 বার আমি পুনরাবৃত্তি করতে পারি না, কারণ আমি 3 বারের বেশি পুনরাবৃত্তি করতে পারি না। সুতরাং আমরা ভি এর আগে একটি আই প্লেন করি যেহেতু আমি ভি এর চেয়ে কম, সুতরাং 1 টি মোট থেকে বিয়োগ করা হয় যা 5 এর সমান হয়। সুতরাং মোট সমষ্টিটি 4 এর সমান হয়।

রোমান লেটকোড সলিউশন এর পূর্ণসংখ্যার জন্য দৃষ্টিভঙ্গি

"রোমানের সাথে পূর্ণসংখ্যা" সমস্যাটি লোভী পদ্ধতিতে সমাধান করা যেতে পারে যেখানে প্রথমে আমরা সংখ্যাটি সর্বোচ্চ সম্ভাব্য সংখ্যায় রূপান্তরিত করার চেষ্টা করি। সমস্যাটির জন্য নিষ্ঠুর বল প্রয়োগ করা সম্ভব নয় কারণ এটি না কার্যকর এবং সাধারণভাবে প্রযোজ্য। এই পদ্ধতিতে আমরা রোমান সংখ্যায় আরও ছোট সংখ্যায় চলে যাই। 4 আমরা রূপান্তর করার চেষ্টা করার সময় এই পদ্ধতিটি ব্যর্থ হবে This এই পদ্ধতিটি 4 বার মুদ্রণ করবে So সুতরাং, আমাদের এটির কাছাকাছি যাওয়ার উপায় খুঁজে নেওয়া দরকার।

ঠিক আছে, আমরা যদি ঘনিষ্ঠভাবে লক্ষ্য করি তবে কয়েকটি ব্যাক্তিগত সম্ভাব্য উপায় আছে যখন আমরা এই ব্যতিক্রমটি দেখতে পারি। এই ব্যতিক্রমগুলি কেবল তখনই হয় যখন আমরা কিছু সংখ্যাকে 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), কারণ আমরা ফলাফলটি খুঁজতে ধ্রুবক পদক্ষেপ ব্যবহার করছি।

স্পেস জটিলতা ity

ও (1), যেহেতু আমরা কেবলমাত্র স্থির সংখ্যক ভেরিয়েবল সংরক্ষণ করেছি এবং যে অ্যারেগুলি আমরা ব্যবহার করেছি তার ধ্রুব আকারও রয়েছে।