पॉव (एक्स, एन) लीटकोड सोल्यूशन


अडचण पातळी मध्यम
वारंवार विचारले अडोब ऍमेझॉन सफरचंद आसन ब्लूमबर्ग हा कोड eBay फेसबुक गोल्डमन Sachs Google संलग्न मायक्रोसॉफ्ट ओरॅकल पोपल उबेर व्हीएमवेअर वॉलमार्ट लॅब
बायनरी शोध गणित

“पॉव (एक्स, एन) लीटकोड सोल्यूशन” या समस्येमध्ये असे म्हटले आहे की आपणास दोन क्रमांक दिले गेले आहेत, त्यातील एक फ्लोटिंग पॉईंट क्रमांक आणि दुसरा पूर्णांक आहे. पूर्णांक घातांक दर्शवितो आणि बेस म्हणजे फ्लोटिंग पॉईंट क्रमांक. पायथ्यावरील घातांकांचे मूल्यांकन केल्यावर आपल्याला मूल्य शोधण्यास सांगितले जाते. आधार नकारात्मक, सकारात्मक किंवा शून्य असू शकतो. घातांक पूर्णांक श्रेणी दरम्यान कुठेही पडून राहू शकतो. आऊटपुटवरही आम्हाला बाधा आहे. आउटपुट -10000 ते +10000 दरम्यान कुठेही असेल. तर काही उदाहरणे पहा.

पॉव (एक्स, एन) लीटकोड सोल्यूशन

उदाहरण

Base: 2
Exponent: 10
Answer: 1024

स्पष्टीकरणः 2 ^ 10 = 104 चे मूल्य असल्याने, उत्तर. याची पुनरावृत्ती 2 वेळा 10 वेळा केल्याने देखील केली जाऊ शकते.

Base: 2
Exponent: -10
Answer: 0.00098

स्पष्टीकरणः उत्तर बदलले गेले आहे कारण घातांकचे मूल्य देखील -10 केले गेले आहे.

क्रूर शक्ती दृष्टीकोन

पॉव (एक्स, एन) लीटकोड सोल्यूशनच्या समस्येसाठी क्रूर शक्ती दृष्टीकोन अतिशय सोपा आहे. आम्हाला केवळ एक्सपोन्टरचे मूल्यांकन करण्याच्या ऑपरेशनचे नक्कल करणे आवश्यक आहे. बेस एक्स्पॉन्टरच्या संख्येच्या गुणाकारांद्वारे सहजपणे मूल्यमापन केले जाऊ शकते. म्हणून आपल्या कोणत्याही आवडत्या प्रोग्रामिंग भाषांमध्ये लूपचा वापर करुन आपण हे सहजपणे नक्कल करू शकतो. लक्षात घेण्याजोगी एक गोष्ट म्हणजे कोपरा प्रकरणे. जेव्हा एकतर घातांक पूर्ण संख्येच्या किमान मूल्याच्या किंवा किमान मूल्याच्या समान असेल पूर्णांक. जेव्हा आपल्याकडे पूर्णांकचे किमान मूल्य म्हणून घातांक असते, तर उत्तर 1 किंवा 0 असू शकते. जर बेस 1 किंवा -1 असेल तर पूर्णांकचे किमान मूल्य म्हणून 1 असेल तर 0 असे उत्तर असेल. त्याचप्रमाणे आपल्याकडे फक्त 1 असू शकते अधिकतम सह पूर्ण संख्येचे मूल्य म्हणून आउटपुटवरील मर्यादा 10000 च्या खाली आहे. या निर्बंधांचा विचार करता आम्ही बेस एक्सपोनेंट टाइम्सच्या गुणाकाराचे अनुरूप ब्रूट फोर्स कोड लिहू शकतो.

पॉवर कोड (x, एन) लीटकोड सोल्यूशन

सी ++ कोड

#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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन), कारण आम्ही बेस एक्सपोनेन्शन वेळा गुणाकार करीत नाही. अशा प्रकारे वेळेची जटिलता रेषात्मक असते.

स्पेस कॉम्प्लेक्सिटी

ओ (1), कारण आपल्याला फक्त उत्तर संग्रहित करावे लागेल, आम्ही एकच व्हेरिएबल वापरु. अशा प्रकारे, जागेची जटिलता स्थिर आहे.

पॉव (एक्स, एन) लीटकोड सोल्यूशनसाठी ऑप्टिमाइझ केलेला दृष्टीकोन

ऑप्टिमाइझ केलेला दृष्टिकोन वेगवान मोड्युलो एक्सपोन्शियेशन अल्गोरिदम वापरतो. आम्ही एकतर रिकर्सिव रीतीने किंवा पुनरावृत्तीने वेगवान मोड्यूलो एक्सपोन्शिएशन कार्यान्वित करू शकतो. वेगवान मोड्युलो एक्सपोन्शिएशनमध्ये, आम्ही बेस 2 च्या पॉवरमध्ये गुणाकार करतो. याचा अर्थ असा होतो की आपण स्वतःच बेस गुणाकार करीत राहू. तर, पहिल्या चरणात, बेस स्वतःचा चौरस बनतो. समजा बेस “बी” द्वारे दर्शविला गेला. तर पहिल्या चरणात ते बी 2 बनते, पुढच्या चरणात ते बी -4 होईल, नंतर बी ^ 8, नंतर बी, 16 आणि अशाच प्रकारे. आता, आम्ही घातांक असलेल्यांशी संबंधित फक्त आधार शक्ती गुणाकार करतो. म्हणून घातांकांना बायनरी फॉरमॅटमध्ये रुपांतरित करा आणि घातांक बायनरी फॉरमॅट नुसार बेसची गुणाकार करणे सुरू ठेवा. उदाहरणार्थ, 3 ^ 6 मोजा. येथे बेस =,, घातांक = b. बायनरी फॉरमॅटमध्ये ver रूपांतरित केल्याने ते ११० बनते. आता पहिल्या टप्प्यात आपण तपासतो की घातांक १. बी 3 बनते. आता मध्ये त्याचे सर्वात कमी सर्वात कमी महत्त्वपूर्ण बिट म्हणून १ आहे, तर आम्ही उत्तरासाठी बी ^ २ गुणाकार करतो. आता उत्तर b ^ 6 बरोबर आहे. बेस नंतर बी ^ 6 बनतो. 110 मध्ये 1 हे तिसरी सर्वात कमी महत्त्वपूर्ण बिट म्हणून 6 असल्यामुळे आम्ही उत्तरासाठी बी -0 गुणाकार करतो. आता उत्तर बी -2 * बी ^ 6 = बी ^ 1 होते. आणि हेच आम्हाला पाहिजे होते. अल्गोरिदम कशी अंमलात आणायची हे शोधण्यासाठी खालील अंमलबजावणी तपासा.

पॉ (x, n) लीटकोड सोल्यूशनसाठी ऑप्टिमाइझ कोड

सी ++ कोड

#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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (लॉगएन), कारण आम्ही वेगवान मोड्यूलो एक्सपोन्शिएशन वापरतो ज्यास बेसवर घातांक मोजण्यासाठी लॉगरिथमिक वेळ लागतो. आम्ही अंतर्ज्ञानाने देखील वेळ जटिलता शोधू शकता. आपण घातांक 0 होईपर्यंत विभाजीत केल्यामुळे हा आवश्यक वेळ लॉगएनवर अवलंबून असतो, जिथे एन घातांक असतो.

स्पेस कॉम्प्लेक्सिटी

ओ (1), उत्तर संग्रहित करण्यासाठी आम्ही एकच व्हेरिएबल वापरला आहे, म्हणून स्पेसची जटिलता स्थिर आहे.