शून्य लीटकोड सोल्यूशनची संख्या कमी करण्यासाठी चरणांची संख्या


अडचण पातळी सोपे
वारंवार विचारले ऍमेझॉन Google एचआरटी मायक्रोसॉफ्ट
बिट मॅनिपुलेशन

शून्य लीटकोड सोल्यूशनची संख्या कमी करण्यासाठी चरणांची संख्या ही एक नमूद करते पूर्णांक. दिलेल्या पूर्णांकास 0 मध्ये रुपांतरित करण्यासाठी किमान चरणांची संख्या शोधा. आपण दोनपैकी एक चरण करू शकता, एकतर 1 वजा करा किंवा पूर्णांक 2 सह विभाजित करू शकता. समस्या सोपी दिसते पण निराकरण करण्यापूर्वी आपण काही उदाहरणे पाहू. .

शून्य लीटकोड सोल्यूशनची संख्या कमी करण्यासाठी चरणांची संख्या

n = 14
6

स्पष्टीकरणः दिलेला पूर्णांक (= 14) ते 0 पर्यंत कमी करण्यासाठी चरणांची किमान संख्या 6 चरण आवश्यक आहे. प्रथम, 14 ने 2 ने विभाजित करा. आता आपल्याकडे 7. बाकी आहे. नंतर आपल्याकडे 1 ही संख्या 6 आहे. आम्ही पुन्हा 2 ने विभाजित करतो. नंतर पूर्णांक (= 1) ते 3 पर्यंत कमी करण्यासाठी आम्ही 0 वेळा वजा करतो.

8
4

स्पष्टीकरणः आम्ही 3 ते 1 कमी करण्यासाठी 8 विभाजित आणि 0 वजाबाकी ऑपरेशन वापरतो. पहिली चाल 8 ते 4 कमी करते, नंतर 4 ते 2, 2 ते 1. नंतर 1 मिळवण्यासाठी आपण 1 वरून फक्त 0 वजा करतो.

शून्य लीटकोड सोल्यूशनची संख्या कमी करण्यासाठी चरण संख्या संख्यासाठी ब्रूट फोर्स दृष्टीकोन

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

शून्य लीटकोड सोल्यूशनची संख्या कमी करण्यासाठी चरणांच्या संख्येसाठी अनुकूलित दृष्टीकोन

समस्या ही प्रमाणित समस्यांपैकी एक आहे, जी मोठ्या प्रमाणात ज्ञात आहे. एखादी विषम संख्या आढळल्यासच आपण 1 वजा केल्यास ही समस्या सहजपणे सोडविली जाऊ शकते. जेव्हा आपल्याला सम संख्या मिळते तेव्हा संख्या 2 ने विभाजित करा. अशाप्रकारे समस्येचे निराकरण पूर्णांक च्या समतेवर अवलंबून असते. संख्या समान असताना आम्ही 2 वरून विभाजीत का करू? १. वजा करण्यापेक्षा अर्धा करून संख्या कमी करणे नेहमीच चांगले किंवा तितकेच चांगले आहे. तर मग आपण विचित्र संख्येचे विभाजन का करीत नाही? कारण मग आपल्याकडे दशांश पूर्णांक पूर्ण होतील जे कोणत्याही प्रकारे या दोन ऑपरेशन्सचा वापर करून 1 पर्यंत कमी करता येणार नाहीत.

शून्य लीटकोड सोल्यूशनची संख्या कमी करण्यासाठी चरणांच्या संख्येसाठी ऑप्टिमाइझ कोड

सी ++ कोड

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

int numberOfSteps (int num) {
    int cnt = 0;
    while(num){
        if(num&1)num--;
        else num/=2;
        cnt++;
    }
    return cnt;
}

int main(){
    cout<<numberOfSteps(14);
}
6

जावा कोड

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

class Main
{
  public static int numberOfSteps (int num) {
        int cnt = 0;
        while(num > 0){
            if(num%2 == 1)num--;
            else num/=2;
            cnt++;
        }
        return cnt;
    }
    
  public static void main (String[] args) throws java.lang.Exception{
    System.out.print(numberOfSteps(14));
  }
}
6

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

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

ओ (लॉगएन), कारण जेव्हा जेव्हा आपल्याला समान संख्या येते तेव्हा आपण पूर्णांक 2 ने भाग करतो. नंतर प्रत्येक विषम संख्या त्यातून 1 वजा करुन सम संख्येमध्ये रूपांतरित केली जाते. अशा प्रकारे वेळेची गुंतागुंत लॉगरिथमिक असल्याचे समोर येते.

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

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