Pow (x, n) लीटकोड समाधान


कठिनाई तह मध्यम
बारम्बार सोधिन्छ एडोब अमेजन एप्पल asana ब्लूमबर्ग eBay फेसबुक Goldman सैक्स गुगल LinkedIn माइक्रोसफ्ट बजेट PayPal Uber VMware वालमार्ट ल्याबहरू
बाइनरी खोज गणित

समस्या "Pow (x, n) लेटकोड समाधान" भन्छ कि तपाईंलाई दुई नम्बर दिइन्छ, जस मध्ये एक फ्लोटिंग पोइन्ट नम्बर र अर्को इन्टिजर हुन्छ। पूर्णांकले घातांकलाई जनाउँछ र आधार फ्लोटिंग पोइन्ट नम्बर हो। हामीलाई आधारमा घाता .्कको मूल्यांकन गरेपछि मान पत्ता लगाउन भनिएको छ। आधार नकारात्मक, सकारात्मक, वा शून्य हुन सक्छ। घाता .्क कुनै पनि पूर्णांकको दायरा बीचमा पर्न सक्छ। हामीलाई आउटपुटमा एक अवरोध पनि दिइन्छ। आउटपुट -10000 देखि +10000 बीचको जहाँसुकै हुनेछ। त्यसो भए, हामी केही उदाहरणहरूमा एक नजर राख्दछौं।

Pow (x, n) लीटकोड समाधान

उदाहरणका

Base: 2
Exponent: 10
Answer: 1024

स्पष्टीकरण: २ ^ १० = १०2 को लागि मान, त्यसैले उत्तर। यसलाई २ १० पटक दोहोर्याएर गुणन गरेर पनि जाँच गर्न सकिन्छ।

Base: 2
Exponent: -10
Answer: 0.00098

स्पष्टीकरण: उत्तर परिवर्तन गरिएको छ किनकि घातांकको मान पनि -१० मा परिवर्तन गरिएको छ।

ब्रुट फोर्स अप्रोच

समस्या Pow (x, n) लीटकोड समाधानको लागि ब्रुट फोर्स दृष्टिकोण एकदम सरल छ। हामीले एक्स्पोनेन्ट्सको मूल्यांकन गर्ने अपरेसन केवल सिमुलेट गर्नु पर्छ। घाता .्क सजिलैसँग आधार घाता संख्यालाई गुणा गरेर मूल्या be्कन गर्न सकिन्छ। त्यसो भए हामी यसलाई सजिलैसँग हाम्रो मनपर्ने प्रोग्रामिंग भाषाहरूमा लुप प्रयोग गरेर सिमुलेट गर्न सक्छौं। ध्यान दिनुहोस् एउटा कुरा, कुनाका केसहरू हुन्। जब कि त घातांक पूर्णांकको अधिकतम मान वा न्यूनतम मानको बराबर हुन्छ पूर्णांक। जब हामीसँग पूर्णांकको न्यूनतम मानको रूपमा घातांक हुन्छौं, उत्तर १ या 1. हुन्छ। यदि आधार १ वा -१ हो, पूर्णांकको न्यूनतम मानको रूपमा एक्स्पोनेन्ट भएमा, १ अन्यथा ० हुन्छ। यस्तै हामीसँग १ मात्र हुन सक्छ। घाता .्कको अधिकतम मानको रूपमा पूर्णाger्कको साथ, आउटपुटमा प्रतिबन्ध १००००० भन्दा तल छ। यी अवरोधहरूलाई विचार गर्दा हामी आधार घाता समयको गुणन अनुकरणको साथ ब्रुट फोर्स कोडको रूपमा लेख्न सक्छौं।

Pow (x, n) लीटकोड समाधानको लागि कोड

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

जटिलता विश्लेषण

समय जटिलता

O (N), किनकि हामी बेस एक्सपोनेन्ट टाइम्स गुणा नगरेसम्म हामी लुप गर्छौं। यस प्रकार समय जटिलता रैखिक छ।

ठाउँ जटिलता

O (१), किनभने हामीले मात्र उत्तर भण्डारण गर्नुपर्दछ, हामी एकल भ्यारीएबल प्रयोग गर्छौं। यसैले, स्थान जटिलता स्थिर छ।

Pow (x, n) लीटकोड समाधानको लागि अनुकूलित दृष्टिकोण

अनुकूलित दृष्टिकोण द्रुत मोड्युलो एक्सपोनेसिएसन एल्गोरिथ्म प्रयोग गर्दछ। हामी छिटो मोडुलो एक्सपोन्टेनेसन या त पुनरावृत्तिक तरिकामा वा पुनरावृत्तिक रूपमा लागू गर्न सक्दछौं। द्रुत मोडुलो एक्सपोनेन्सेसनमा, हामी २ लाई पावरमा आधार गुणा गर्छौं। यसको मतलब हामी आफैंले आधार गुणा गरिरहन्छौं भन्ने हो। त्यसो भए, पहिलो चरणमा, आधार आफै वर्गफल हुन्छ। मानौं बेस "बी" द्वारा दर्साइएको आधार। त्यसो भए पहिलो चरणमा यो बी ^ २ हुन्छ, अर्को चरणमा यो बी ^ become, त्यसपछि बी ^ will, त्यसपछि बी ^ १ become, र यस्तै हुनेछ। अब हामी घाता powers्गमा आधारभूत शक्तिहरू मात्र गुणा गर्दछौं। त्यसो भए, एक्स्पोनेन्टलाई बाइनरी ढाँचामा रूपान्तरण गर्नुहोस् र घाता .्क बाइनरी ढाँचा अनुसार आधारहरू गुणा गर्न जारी राख्नुहोस्। उदाहरण को लागी, 2 ^ 2 गणना गर्नुहोस्। यहाँ आधार =,, घातांक = b बाइनरी ढाँचामा ver रूपान्तरणले यसलाई ११० बनाउँछ। अब, पहिलो चरणमा हामी जाँच गर्छौं घातांक १ छ। 4 यसको पहिलो न्यूनतम बिटको रूपमा ० छ, त्यसैले हामी यसलाई छोड्यौं र बेसलाई छोड्छौं। बी ^ २ हुन्छ। अब, को १ यसको दोस्रो सबैभन्दा कम महत्त्वपूर्ण बिटको रूपमा छ, त्यसैले हामी बी ^ २ लाई जवाफमा गुणा गर्छौं। अब उत्तर b ^ २ बराबर छ। आधार त्यसपछि b ^ 8 हुन्छ। किनकि सँग यसको 16rd न्यूनतम महत्त्वपूर्ण बिटको रूपमा १ छ, हामी उत्तरमा b ^ multip गुणा गर्दछौं। अब उत्तर b ^ 3 * b ^ 6 = b ^ 3 हुन्छ। र यो हामी चाहन्थ्यौं। एल्गोरिथ्म कसरी कार्यान्वयन गर्ने भन्ने बारे तलको कार्यान्वयन जाँच गर्नुहोस्।

पॉ (x, n) लीटकोड समाधानको लागि अनुकूलित कोड

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

जटिलता विश्लेषण

समय जटिलता

O (logN), किनकि हामीले द्रुत मोडुलो एक्सपोनेन्सेसन प्रयोग गर्‍यौं जुन बेसमा घाता .्कको गणना गर्न लगारिथमिक समय लिन्छ। हामी पनि सहजै समय जटिलता पाउन सक्छौं। किनकि हामीले घाता ० लाई विभाजित गरिसकेका छौं यो ० नहुन्जेलसम्म लाग्ने समय लगN मा निर्भर हुन्छ, जहाँ N घातांक हुन्छ।

ठाउँ जटिलता

O (१), किनकि हामीले उत्तर भण्डार गर्न एकल चर प्रयोग गरेका छौं, स्पेस जटिलता स्थिर छ।