वैध परफेक्ट स्क्वेअर लीटकोड सोल्यूशन


अडचण पातळी सोपे
वारंवार विचारले ऍमेझॉन
लेटकोड

हे पोस्ट वैध परफेक्ट स्क्वेअर लीटकोड सोल्यूशनवर आहे

समस्या विधान

“वैध परफेक्ट स्क्वेअर” या समस्येमध्ये आम्हाला “num” क्रमांक देण्यात आला आहे आणि ही संख्या योग्य वर्ग आहे की नाही हे तपासण्याची गरज आहे. बिल्ट-इन स्क्वार्ट फंक्शन न वापरता हे तपासून पहा.

जर संख्या एक परिपूर्ण वर्ग असेल तर आपण खर्‍यास परत येऊ अन्यथा आपण खोटे परत करू.

उदाहरण

num = 25
true

स्पष्टीकरण:

वैध परफेक्ट स्क्वेअर लीटकोड सोल्यूशन

25 हा एक वैध परिपूर्ण चौरस आहे कारण त्याचा वर्गमूल 5 आहे. तर उत्तर खरे होईल.

दृष्टीकोन

आपण अंगभूत फंक्शन्स वापरू शकत नाही म्हणून, या समस्येचे निराकरण करण्याचा मूलभूत दृष्टीकोन म्हणजे प्रत्येक संख्या 1 ते num पर्यंत तपासून त्याचा वर्ग शोधणे नंतर त्याचा वर्ग क्रमांक इतका आहे का ते तपासा. जर चौरस num च्या बरोबर असेल तर num हा एक वैध परफेक्ट स्क्वेअर असेल तर आपण true परत येऊ.

प्रत्येक नंबरची रेखीय तपासणी करुनही आम्ही a वापरुन द्रावण सुधारू शकतो बायनरी शोध दृष्टीकोन. या दृष्टीकोनातून, आम्हाला आमची शोध श्रेणी, प्रारंभ बिंदू आणि अंतिम बिंदू ठरविणे आवश्यक आहे.

  1. प्रारंभ बिंदू 1 असेल.
  2. शेवटचा बिंदू क्रमांक असेल कारण संख्यांपेक्षा मोठ्या संख्येचा वर्ग नेहमीच संख्येपेक्षा मोठा असेल.
  3. तेव्हाची श्रेणी बायनरी शोध 1 ते संख्या आहे.
  4. आता आपल्याला मिडचा वर्ग मिळेल. जर चौरस संख्या बरोबर असेल तर आपण दुसर्‍या बरोबर जाऊ.
    1. चौरस संख्यापेक्षा मोठा असल्यास आपला शेवटचा बिंदू मध्य -1 पर्यंत कमी होईल.
    2. अन्यथा प्रारंभ बिंदू मधला +1 होईल.
  5. शेवटी जर संख्या कोणत्याही संख्येच्या संख्येशी जुळत नसेल तर आपण चुकीचे परत येऊ.

कोड

वैध परफेक्ट स्क्वेअर लीटकोड सोल्यूशनसाठी सी ++ कोड

#include <bits/stdc++.h> 
using namespace std; 
    bool isPerfectSquare(int num) {
        int s=1,e=num;
        while(s<=e)
        {
            long long int mid=s+(e-s)/2;
            if(mid*mid==num)
                return true;
            else if(mid*mid>num)
             e=mid-1;
            else
                s=mid+1;
        }
        return false;
    }
int main() 
{ 
 int num=25;
 cout<<boolalpha;
 cout<<isPerfectSquare(num)<<endl; 
 return 0;
}
true

वैध परफेक्ट स्क्वेअर लेटकोड सोल्यूशनसाठी जावा कोड

import java.util.Arrays; 
public class Tutorialcup {
    public static  boolean isPerfectSquare(int num){
    long s=1,e=num;
        while(s<=e)
        {
            long mid=s+(e-s)/2;
            if(mid*mid==num)
                return true;
            else if(mid*mid>num)
             e=mid-1;
            else
                s=mid+1;
        }
        return false;
    }
  public static void main(String[] args) {
    int num=25;
    boolean ans=  isPerfectSquare(num);
    System.out.println(ans);
  }
}
true

वैध परफेक्ट स्क्वेअर लीटकोड सोल्यूशनचे जटिलता विश्लेषण

वेळ गुंतागुंत

वरील कोडची वेळ जटिलता आहे ओ (लॉगइन). येथे n ही num ची व्हॅल्यू आहे.

जागेची जटिलता

वरील कोडची स्पेस कॉम्प्लेक्सिटी आहे ओ (1) कारण आम्ही उत्तर संग्रहित करण्यासाठी फक्त एक व्हेरिएबल वापरत आहोत.

संदर्भ