မှတ်ချက် – ဒီ Post သည် Algorithm Interview Preparation အပိုင်းဆက်ဖြစ်သည်။

ကျနော်တို့ဒီနေ့ရှင်းမယ့် ပြဿနာက 1291. Sequential Digits ဆိုတဲ့ leetcode question ဘဲဖြစ်ပါတယ်။

An integer has sequential digits if and only if each digit in the number is one more than the previous digit.

Return a sorted list of all the integers in the range [low, high] inclusive that have sequential digits.

 

Example 1:

Input: low = 100, high = 300
Output: [123,234]
Example 2:

Input: low = 1000, high = 13000
Output: [1234,2345,3456,4567,5678,6789,12345]
 

Constraints:

10 <= low <= high <= 10^9

ကျနော်တို့မေးခွန်းကိုတချက်နားလည်အောင်ကြည့်လိုက်ရအောင်။ သူကပထမဆုံး sequential digits ကိုရှင်းပြထားတယ် ရှေ့ကနံပါတ်ထက်နောက်ကနံပါတ်ကပိုကြီးမှ sequential digits ဖြစ်တယ်ဆိုပီးရှင်းပြထားတယ်။ သူလိုချင်တာက [low, high] ကြားက sequentails digits တွေကို return ပြန်ပေးပါတဲ့ အဲ့ပြန်လာတဲ့ကောင်တွေက sorted ဖြစ်နေရပါမယ်တဲ့။

ဥပမာတွေကလဲရှင်းပါတယ် 100 နှင့် 300 ကြားက sequentials တွေက 123, 234။

အောက်မှာအဖြေကိုတချက်ကြည့်ကြည့်ရအောင်။ အဖြေမကြည့်ခင်ကိုယ်ပိုင် ကြိုးစားပီးဖြေကြည့်ဖို့အကြံပေးလိုပါတယ်။

---

ဒီကောင်ကိုဖြေဖို့ ကျနော်စဥ်းစားမိတာလေးတွေတချက်ပြန် ရှယ်ပါ့မယ်။ ဥပမာကိုကြည့်လိုက်တော့ 100 ကနေ 300 ဆို 123, 234 ဆိုတော့ ကျနော်တို့ 123 ကိုရှာနိုင်ပီဆိုရင် 234 ကိုထက်ရှာလို့ရပီ။

ဥပမာမြင်အောင်ပြရမယ်ဆိုရင် ကျနော်ကဒီလိုစဥ်းစားလိုက်တာ

100 ကနေ 300 ကြားဆိုတော့ sequentails က 123, ပီးသွားရင် 234။ first sequential ရှာပီးတော့နောက်ဟာတွေကို sequeunce လိုက်တိုးတာ အဲ့လိုတိုးတာအများဆုံးက 1 ကနေ 9 ထိဘဲ။

ကျနော်တို့သူပေးထားတဲ့ ဒုတိယဥပမာကိုကြည့်လိုက်မယ်ဆိုရင် 1000 ကနေ 13000 ကြားဆိုတော့။

1234,2345,3456,4567,5678,6789,12345

ဒီမှာတခုသတိထားမိတာက 6789 ပီးသွားတော့ sequence ဖြစ်ဖို့ဆို 12345 လာရမှာ။ 67890 မဟုတ်ဘူး။ အဲ့လိုကောင်ကို approach လုပ်ဖို့ စဥ်းစားမိတာက ကျနော်တို့က base 10 သုံးတာဆိုတော့ base 10 နဲ့မြှောက်ပီးတော့ 1 ပေါင်းလိုက်ရင် sequence ရတယ်။ ဥပမာနဲ့မြင်အောင်အောက်မှာတချက်ပြကြည့်ကြည့်မယ်။

100

100 ကို ကျနော်တို့က 1 ကနေကိုး loop ပတ်ပီး sequence ရှာမယ်။

// sequential ရှာဖို့ 1 ကနေ 9 ကို loop ပတ်ပီးရှာ
for(let startDigit = 1; startDigit <= 9; startDigit++) {
    let num = startDigit;

    for(let nextDigit = startDigit + 1; nextDigit <= 9; nextDigit++) {
        // 1 ကို 10 နှင့်မြှောက်လိုက်ရင် 10 နောက်လာမယ့်နံပါတ်က 2 ဖြစ်တော့သူနဲ့ပေါင်းလိုက်တော့ 12။ အဲ့လိုနည်းနှင့် sequential number ရမယ် 
        num = num * 10 + nextDigit;
        console.log(num)
    }
}

အဲ့ကုဒ်ကို log ထုတ်ကြည့်ရင် sequential နံပတ်တွေအများကြီးလာမယ်။ ကျနော်တို့လိုချင်တာက low နှင့် high ကြားဆိုတော့ အဲ့ကောင်ကိုဘဲ filter လုပ်လိုက်မယ်ဆိုရင် ကျနော်တို့လိုချင်တာရပီ။ base 10 နှင့်ရှင်းပြတာသိပ်ပီးနားမလည်ဘူးဆိုရင် အပေါ်ကကုဒ်ကို run ကြည့်တာပိုပီးမြင်သွားလိမ့်မယ်။

အောက်မှာ solution အပြည့်အစုံကြည့်လိုက်ရအောင်

function sequentialDigits(low, high) {
  const result = [];

  for (let startDigit = 1; startDigit <= 9; startDigit++) {
    let num = startDigit;

    for (let nextDigit = startDigit + 1; nextDigit <= 9; nextDigit++) {
      // 1 ကို 10 နှင့်မြှောက်လိုက်ရင် 10 နောက်လာမယ့်နံပါတ်က 2 ဖြစ်တော့သူနဲ့ပေါင်းလိုက်တော့ 12။ အဲ့လိုနည်းနှင့် sequential number ရမယ်
      num = num * 10 + nextDigit;

      if (num >= low && num <= high) {
        result.push(num);
      }
    }
  }

  return result.sort((a, b) => a - b);
}

နောက်ဆုံးရလာတဲ့အဖြေကို sort လုပ်လိုက်တယ်။ sort ဘာလို့လုပ်ရလဲဆိုတော့ sorted ဖြစ်မနေဘူး ကျနော်တို့ loop ပုံစံကိုကြည့်ရင် sorted ဖြစ်နေရမယ်လို့ထင်နေတက်တယ်။ ကိုယ်တိုင် sort မလုပ်တဲ့ result ကိုတချက်စမ်းကြည့်ကြည့်ရင်ပိုပီးမြင်သာသွားပါလိမ့်မယ်။ ဒီလောက်ဆိုသေချာရှင်းပီလို့ထင်ပါတယ်။ တကယ်လို့သေချာမျက်လုံးထဲမမြင်သေးဘူးဆိုရင် log ထုတ်ကြည့်တာ debugger ထုတ်ပီးတဖြေးဖြေးဘယ်လို process ဖြစ်သွားတာလဲဆိုတာကိုလိုက်ကြည့်ရင်ပိုပီးနားလည်ရလွယ်ပါလိမ့်မယ်။

Time and Space က O(1) ပါ။ ဟာ loop တွေကော sort တွေကော ဘယ်လိုဖြစ်ပီး O(1) လဲဆိုပီးတော့တွေးနိုင်ပါတယ်။ Loop က 1 ကနေ 9 ထိဘဲ loop တာဖြစ်တယ် သူ့မေးခွန်း Constraints အရဆိုရင် max က 123456789 ထိဘဲရှိမှာ အဲ့တော့ input data size ပေါ်မူတည်ပီး grow မဖြစ်ဘူး။ နောက် Space ကလဲအဲ့အတိုင်းဘဲ။