C++-এ মিসিং রেঞ্জ খুঁজে বের করা

ধরা যাক একটি সর্ট করা ইন্টিজার অ্যারে nums আছে, যার এলিমেন্টের রেঞ্জ [lower, upper]। আমাদের মিসিং রেঞ্জগুলো বের করতে হবে।

যেমন, nums = [0, 1, 3, 50, 75], lower = 0, upper = 99 হলে, আউটপুট হবে ["2", "4->49", "51->74", "76->99"]

সমাধানের ধাপগুলো:

• ডুপ্লিকেট রিমুভ করে nums তৈরি করব

• curr := lower, i := 0

• while curr <= upper:

  • যদি nums[i] == curr হয়, তবে i++, curr++

  • অন্যথায়, একটি রেঞ্জ শুরু করব:

    • temp := to_string(curr), curr++

    • যদি পরবর্তী এলিমেন্ট পাওয়া যায়, তবে সিঙ্গেল নাম্বার হিসেবে যোগ করব

    • অন্যথায় রেঞ্জ তৈরি করব "->" দিয়ে

• রেজাল্ট রিটার্ন করব

উদাহরণ

নিচের কোডটি দেখুন −

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

void print_vector(vector<string> v) {
    cout << "[";
    for(int i = 0; i < v.size(); i++) {
        cout << v[i] << ", ";
    }
    cout << "]" << endl;
}

class Solution {
public:
    vector<string> findMissingRanges(vector<int>& t, int lower, int upper) {
        vector<int> nums;
        set<long long int> v;
        for(int i = 0; i < t.size(); i++) {
            if(!v.count(t[i])) {
                v.insert(t[i]);
                nums.push_back(t[i]);
            }
        }
        vector<string> ret;
        long long int curr = lower;
        int i = 0;
        int n = nums.size();
        while(curr <= upper) {
            if(i < n && nums[i] == curr) {
                i++;
                curr++;
            } else {
                string temp = to_string(curr);
                curr++;
                if(i < n && nums[i] == curr) {
                    ret.push_back(temp);
                    continue;
                } else {
                    if(i == n) {
                        if(curr <= upper) {
                            temp += "->";
                            temp += to_string(upper);
                            curr = (long long int)upper + 1;
                        }
                        ret.push_back(temp);
                    } else {
                        temp += "->";
                        curr = nums[i];
                        temp += to_string(curr - 1);
                        curr = nums[i];
                        ret.push_back(temp);
                    }
                }
            }
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector<int> v = {0,1,3,50,75};
    print_vector(ob.findMissingRanges(v, 0, 99));
}

ইনপুট

{0,1,3,50,75}, 0, 99

আউটপুট

[2, 4->49, 51->74, 76->99, ]