Pow (x, n) Leetcode ဖြေရှင်းချက်


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် Adobe က အမေဇုံ Apple Asana ဟာ ဘလွန်းဘာ့ဂ် ကို eBay Facebook က Goldman Sachs Google LinkedIn တို့ Microsoft က Oracle က PayPal က Uber VMware က Walmart ဓာတ်ခွဲခန်းများ
Binary Search သင်္ချာ

“ Pow (x, n) Leetcode Solution” ပြproblemနာကသင့်အားနံပါတ်နှစ်ခုစီပေးထားသည်။ တစ်ခုမှာ floating-point နံပါတ်တစ်ဖြစ်ပြီးကိန်းတစ်ခု။ ကိန်းပြည့်ကိန်းထပ်ကိန်းကိုရည်ညွှန်းတယ်။ ထပ်ကိန်းကိုအခြေခံပြီးတွက်ချက်ပြီးတဲ့အခါမှာတန်ဖိုးကိုရှာဖို့ပြောတယ်။ အခြေဟာအနုတ်၊ အပေါင်း၊ သုညဖြစ်နိုင်တယ်။ ထပ်ကိန်းသည်ကိန်းတစ်ခု၏အကြားရှိမည်သည့်နေရာတွင်မဆိုတည်ရှိသည်။ ကျနော်တို့ကိုလည်း output ကိုအပေါ်တစ် ဦး သတ်ပေးထားကြသည်။ output ကို -10000 မှ +10000 အကြားဘယ်နေရာမှာမဆိုဖြစ်လိမ့်မည်။ ဒါဆိုဥပမာအချို့ကိုကြည့်ရအောင်။

Pow (x, n) Leetcode ဖြေရှင်းချက်

နမူနာ

Base: 2
Exponent: 10
Answer: 1024

ရှင်းလင်းချက်: 2 ^ 10 = 104 အတွက်ဒီနေရာမှာအဖြေအတွက်တန်ဖိုးကတည်းက။ ၎င်းကိုထပ်ခါတလဲလဲမြှောက်ခြင်းအားဖြင့် ၁၀ ဆကြိမ်လည်းစစ်ဆေးနိုင်သည်။

Base: 2
Exponent: -10
Answer: 0.00098

ရှင်းလင်းချက် - ထပ်ကိန်း၏တန်ဖိုးကိုလည်း -10 အဖြစ်ပြောင်း ထား၍ ဖြစ်သောကြောင့်အဖြေမှာပြောင်းလဲသွားသည်။

Brute Force ချဉ်းကပ်မှု

ပြ(နာအတွက် Brute Force ချဉ်းကပ်မှု Pow (x, n) Leetcode Solution သည်အလွန်ရိုးရှင်းပါသည်။ ထပ်ညွန်းကိန်းများတွက်ချက်ခြင်း၏စစ်ဆင်ရေးကိုကျွန်ုပ်တို့ရုံလုပ်ရန်လိုသည်။ ထပ်ကိန်းကို Base ထပ်ကိန်းထပ်ကိန်းကိုမြှောက်ခြင်းဖြင့်လွယ်ကူစွာအကဲဖြတ်နိုင်သည်။ ဒါကြောင့်ငါတို့အကြိုက်ဆုံးပရိုဂရမ်ဘာသာစကားတစ်ခုခုမှာကွင်းဆက်တစ်ခုသုံးပြီးဒါကိုအလွယ်တကူလုပ်နိုင်တယ်။ မှတ်သားရမည့်အရာတစ်ခုမှာထောင့်ချိုးကိစ္စများဖြစ်သည်။ ထပ်ကိန်းသည်အမြင့်ဆုံးကိန်းသို့မဟုတ်အနိမ့်ဆုံးတန်ဖိုးနှင့်ညီမျှသောအခါ ကိန်း။ ထပ်ကိန်းကိုအနိမ့်ဆုံးကိန်းအဖြစ်သတ်မှတ်လျှင်၊ အဖြေသည် ၁ (သို့) သုညဖြစ်နိုင်သည်။ အခြေခံသည် ၁ သို့မဟုတ် ၁ ဖြစ်ပါကထပ်ညွန်းကိန်း၏အနိမ့်ဆုံးတန်ဖိုးအနေဖြင့်အဖြေသည် ၁ မဟုတ်လျှင် ၀ ဖြစ်နိုင်သည်။ အလားတူစွာကျွန်ုပ်တို့သည် ၁ ခုသာရှိနိုင်သည်။ exponent သည်ကိန်း၏အမြင့်ဆုံးတန်ဖိုးဖြစ်သည်။ အဘယ့်ကြောင့်ဆိုသော် output ပေါ်ရှိကန့်သတ်ချက်များသည် ၁၀၀၀၀ အောက်တွင်ရှိသည်။ ထိုကန့်သတ်ချက်များကိုထည့်တွက်လျှင် brute force code အနေနှင့်အခြေထပ်ကိန်းထပ်ကိန်းကိုမြှောက်ခြင်းဖြင့်ရေးနိုင်သည်။

Pow များအတွက်ကုဒ် (x, n) Leetcode ဖြေရှင်းချက်

C ++ ကုဒ်

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

double myPow(double x, int n) {
    if (n == INT_MAX) return x;
    else if (n == INT_MIN) return (x == 1 || x == -1) ? 1 : 0;
    if(n<0) x=1/x, n*=-1;
    double ans = 1;
    for(int i=0;i<n;i++)
        ans = ans*x;
    return ans;
}

int main(){
    cout<<myPow(2, 10);
}
1024

ဂျာဗားကုဒ်

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

class Solution {
    public static double myPow(double x, int n) {
        if (n == Integer.MAX_VALUE) return x;
        else if (n == Integer.MIN_VALUE) return (x == 1 || x == -1) ? 1 : 0;
        if(n<0) {
            x=1/x;
            n*=-1;
        }
        double ans = 1;
        for(int i=0;i<n;i++)
            ans = ans*x;
        return ans;
    }
    
    public static void main(String[] args){
    	System.out.println(myPow(2, 10));
    }
};
1024.0

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (N)၊ ဘာလို့လဲဆိုတော့ငါတို့ကိန်းဂဏန်းကိုမြှောက်တဲ့အထိ loop လုပ်တယ်။ ထို့ကြောင့်အချိန်ရှုပ်ထွေးမှုမှာ linear ဖြစ်သည်။

အာကာသရှုပ်ထွေးမှု

အို (၁)၊ ဘာလို့လဲဆိုတော့ကျွန်တော်တို့ကအဖြေတစ်ခုတည်းကိုပဲသိမ်းထားရမယ်၊ variable တစ်ခုတည်းသုံးတယ်။ ထို့ကြောင့်အာကာသရှုပ်ထွေးစဉ်ဆက်မပြတ်ဖြစ်ပါတယ်။

Pow (x, n) Leetcode Solution အတွက်အကောင်းဆုံးချဉ်းကပ်မှု

အဆိုပါ optimized ချဉ်းကပ်အစာရှောင်ခြင်း modulo အဆ algorithm ကိုအသုံးပြုသည်။ ကျွန်ုပ်တို့သည်မြန်ဆန်သော modulo ထပ်ကိန်းကို recursive ပုံစံဖြင့်ဖြစ်စေ၊ အမြန် modulo ထပ်ကိန်းတွင်အခြေခံကို 2 ၏မြှောက်ခြင်းဖြင့်မြှောက်ခြင်းအားဖြင့်ကျွန်ုပ်တို့သည်အခြေခံကိုသူ့ဟာသူ ဆက်၍ မြှောက်မည်ဟုဆိုလိုသည်။ ဒါကြောင့်ပထမခြေလှမ်းမှာအခြေစိုက်စခန်းသည်သူ့ဟာသူနှစ်ထပ်ကိန်းဖြစ်လာသည်။ Base ကို“ b” လို့ခေါ်တယ်ဆိုပါစို့။ ဒီတော့ပထမခြေလှမ်းမှာ b ^ 2 ဖြစ်လာတယ်၊ နောက်အဆင့်မှာတော့ b ^ 4၊ b ^ 8၊ b ^ 16 စသည်။ အခုငါတို့ထပ်ညွှန်းကိန်းနှင့်သက်ဆိုင်သောစွမ်းအားများကိုသာမြှောက်သည်။ ဒီတော့ exponent ကို binary format နဲ့ပြောင်းပြီးထပ်ကိန်း binary format နဲ့အတူထပ်ပြီးမြှောက်ပါ။ ဥပမာအားဖြင့်၊ ၃ ^ ၆ ကိုတွက်ချက်ပါ။ ဒီနေရာမှာ base = 3, exponent = 6. 3 ကို binary format နဲ့ပြောင်းခြင်းက 6 ဖြစ်တယ်။ အခုပထမအဆင့်မှာတော့ exponent ဆိုတာ 6 ရှိမရှိစစ်ဆေးပါတယ်။ ခ ^ 110 ဖြစ်လာသည်။ အခု ၆ မှာ 1 ရဲ့ဒုတိယအနိမ့်ဆုံးအနိမ့်ဆုံး bit ဖြစ်သွားပြီ၊ ဒါကြောင့်အဖြေကို b ^ 6 နဲ့မြှောက်တယ်။ အခုအဖြေက b ^ 0 နဲ့ညီတယ်။ ခြေရင်းထို့နောက်ခ ^ 2 ဖြစ်လာသည်။ ၆ မှာ ၁ ခုသည်အနိမ့်ဆုံး ၃ ခုအနိမ့်အမြင့်ဖြစ်သည့်အတွက်အဖြေကို b ^ 6 မြှောက်သည်။ အဖြေသည်ယခုခ ^ 1 * ခ ^ 2 = b ^ 2 ဖြစ်လာသည်။ ဒါကငါတို့လိုချင်တာပဲ။ algorithm ကိုမည်သို့အကောင်အထည်ဖော်ရမည်ကိုရှာဖွေရန်အောက်တွင်ဖော်ပြထားသောအကောင်အထည်ဖော်မှုကိုစစ်ဆေးပါ။

Pow (x, n) Leetcode Solution အတွက်အကောင်းဆုံးကုဒ်

C ++ ကုဒ်

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

double myPow(double x, int n) {
    if (n == INT_MAX) return x;
    else if (n == INT_MIN) return (x == 1 || x == -1) ? 1 : 0;
    if(n<0) x=1/x, n*=-1;
    double ans = 1;
    while(n>0){
        if(n&1)
            ans *= x;
        x = x*x;
        n = n>>1;
    }
    return ans;
}

int main(){
    cout<<myPow(2, 10);
}
1024

ဂျာဗားကုဒ်

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

class Solution {
    public static double myPow(double x, int n) {
        if (n == Integer.MAX_VALUE) return x;
        else if (n == Integer.MIN_VALUE) return (x == 1 || x == -1) ? 1 : 0;
        if(n<0) {
            x=1/x;
            n*=-1;
        }
        double ans = 1;
        while (n>0){
            if(n%2 == 1) ans = ans*x;
            x = x*x;
            n = n>>1;
        }
        return ans;
    }
    
    public static void main(String[] args){
    	System.out.println(myPow(2, 10));
    }
};
1024

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (logN)၊ ဘာဖြစ်လို့လဲဆိုတော့ငါတို့က logarithmic time ကိုအခြေခံပြီး exponent ကို base ပေါ်မှာတွက်ချက်ဖို့အစာရှောင်ခြင်း modulo ထပ်ညွှန်းကိုသုံးခဲ့တယ်။ ငါတို့သည်လည်းအလိုလိုအချိန်ရှုပ်ထွေးရှာတွေ့နိုင်ပါသည်။ ကျနော်တို့ကထပ်ကိန်းကို 0 ဖြစ်လာတဲ့အထိခွဲဝေပြီးကတည်းကလိုအပ်သောအချိန်သည် logN, ပေါ်တွင်မူတည်သည် N သည်ထပ်ကိန်းဖြစ်သည်။

အာကာသရှုပ်ထွေးမှု

အို (၁)၊ အဖြေကိုသိမ်းဆည်းရန် variable တစ်ခုတည်းကိုကျွန်ုပ်တို့အသုံးပြုခဲ့ကြသောကြောင့်အာကာသ၏ရှုပ်ထွေးမှုသည်အမြဲတမ်းဖြစ်သည်။