शून्य लेटकोड समाधानमा संख्या घटाउन चरणहरूको संख्या


कठिनाई तह सजिलो
बारम्बार सोधिन्छ अमेजन गुगल HRT माइक्रोसफ्ट
बिट हेरफेर

शून्य लेटकोड समाधानमा संख्या घटाउने चरणहरूको समस्या संख्याले बताएको छ कि पूर्णांक। दिइएको पूर्णांक ० मा रूपान्तरण गर्न चरणहरूको न्यूनतम संख्या पत्ता लगाउनुहोस्। तपाईं दुई चरणहरू मध्ये कुनै एक प्रदर्शन गर्न सक्नुहुन्छ, १ घटाउनुहोस् वा पूर्णांक २ लाई दुईमा विभाजन गर्नुहोस्। समस्या सरल देखिन्छ तर समाधानमा जानु अघि हामी केही उदाहरणहरू देख्नेछौं। ।

शून्य लेटकोड समाधानमा संख्या घटाउन चरणहरूको संख्या

n = 14
6

स्पष्टीकरण: दिइएको पूर्णांक (= 14) लाई ० लाई कम गर्न न्यूनतम चरणहरूको 0 चरणहरू आवश्यक पर्दछ। पहिले १ 6 लाई २ लाई २ विभाजन गर्नुहोस्। अब हामी with लाई छोड्छौं। त्यसपछि हामी १ घटाउँछौं। अब हामीसँग संख्या 14. छ। हामी फेरि २ लाई भाग गर्छौं। त्यसपछि हामी १ गुणा घटाउँछ पूर्णांक (=)) लाई ० लाई घटाउन।

8
4

स्पष्टीकरण: हामी divide देखि ० लाई कम गर्न divide डिभाइड र १ घटाउ अपरेशन प्रयोग गर्छौं। पहिलो चाल 3 देखि reduces लाई कम हुन्छ, त्यसपछि to देखि २, २ देखि १। त्यसपछि हामी केवल ० प्राप्त गर्न १ बाट १ घटाउँछौं।

शून्य लीटकोड समाधानमा संख्या घटाउन चरणहरूको संख्याको लागि ब्रुट फोर्स दृष्टिकोण

समस्या धेरै मानक छ र विभिन्न परीक्षणहरु मा धेरै पटक सोधिन्छ। समस्याको लागि बल बल समाधान समय सीमा अन्तर्गत समस्या समाधान गर्न पर्याप्त छैन। ब्रुट फोर्स समाधान समाधानको लागि रिकर्सन प्रयोग गर्दछ। प्रत्येक पूर्णांकको लागि, किनकि हामीसँग दुईवटा सम्भावित अपरेशनहरू छन्। हामी ती दुबै प्रदर्शन गर्छौं र फेरी परिमार्जन गरिएको पूर्णांकका लागि कल गर्दछौं। समाधान को लागी समय जटिलता घाती हुन्छ यसैले ठूला इनपुटका लागि कुशल हुँदैन। समाधान हुँदा कोडिड रनटाइम त्रुटिमा परिणत हुन्छ किनकि दशमलव भाग भएको नम्बरहरू कहिले पनि ० मा कम गर्न सक्षम हुँदैनन्।

शून्य लेटकोड समाधानमा संख्या घटाउन चरणहरूको संख्याको लागि अनुकूलित दृष्टिकोण

समस्या एक मानक समस्या हो, जुन धेरै व्यापक रूपमा चिनिन्छ। समस्या सजिलैसँग समाधान गर्न सकिन्छ यदि हामीले १ घटाउछ मात्र जब हामी बिजोर नम्बर भेट्छौं। र संख्या २ लाई भाग गर्नुहोस्, जब हामी समान संख्या पाउँछौं। यसैले समस्याको समाधान पूर्णांकको समानतामा निर्भर हुन्छ। हामी संख्या २ भएको बराबरी किन गर्छौं? किनभने यो सँधै १ को घटाई भन्दा आधा बनाएर यो संख्यालाई कम गर्न राम्रो वा समान रूपमा राम्रो छ। त्यसोभए हामी किन बेजोड नम्बरहरू विभाजन गर्दैनौं? किनभने तब हामीसँग दशमलव पूर्णांक हुन्छ, जुन ० मा कम गर्न सकिदैन यी दुई अपरेशनहरू कुनै पनि हिसाबले प्रयोग गरेर।

शून्य लेटकोड समाधानमा संख्या घटाउन चरणहरूको संख्याका लागि अनुकूलित कोड

C ++ कोड

#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

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

समय जटिलता

O (logN), किनकि हामी पूर्णांकलाई २ ले भाग गर्दछौं जब हामी समान नम्बर पाउँछौं। प्रत्येक बिजोर नम्बर यसबाट १ घटाएर सम संख्यामा रूपान्तरण हुन्छ। यसैले समय जटिलता लघुगणिक हुन बाहिर आउँछ।

ठाउँ जटिलता

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