शून्य लिटकोड समाधान के लिए एक संख्या को कम करने के लिए कदमों की संख्या


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना गूगल एचआरटी माइक्रोसॉफ्ट
बिट मैनिपुलेशन

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

शून्य लिटकोड समाधान के लिए एक संख्या को कम करने के लिए कदमों की संख्या

n = 14
6

स्पष्टीकरण: दिए गए पूर्णांक (= 14) को कम करने के लिए चरणों की न्यूनतम संख्या 0 चरणों की आवश्यकता है। सबसे पहले, 6 को 14 से विभाजित करें। अब हम 2 के साथ बचे हैं। फिर हम 7. घटाते हैं। अब हमारे पास संख्या है। 1. हम फिर से 6 से विभाजित करते हैं। फिर पूर्णांक (= 2) को कम करने के लिए 1 से घटाकर 3 को घटा देते हैं।

8
4

स्पष्टीकरण: हम 3 से 1. को कम करने के लिए 8 डिवाइड और 0 घटाव ऑपरेशन का उपयोग करते हैं। पहली चाल 8 से 4 कम हो जाती है, फिर 4 से 2, 2 से 1. फिर हम 1 पाने के लिए 1 से 0 को घटाते हैं।

शून्य लेटेकोड समाधान के लिए एक संख्या को कम करने के लिए कदम की संख्या के लिए ब्रूट बल दृष्टिकोण

समस्या बहुत मानक है और कई बार विभिन्न परीक्षणों में पूछा जा चुका है। समस्या के लिए जानवर बल समाधान समय सीमा के तहत समस्या को हल करने के लिए पर्याप्त नहीं है। ब्रूट बल समाधान के लिए पुनरावृत्ति का उपयोग करता है। प्रत्येक पूर्णांक के लिए, चूंकि हमारे पास दो संभावित ऑपरेशन हैं। हम दोनों का प्रदर्शन करते हैं और फिर संशोधित पूर्णांक के लिए पुनरावर्ती कॉल करते हैं। समाधान के लिए समय जटिलता घातीय होगी इसलिए बड़े इनपुट के लिए कुशल नहीं है। जब कोडित किया जाता है तो समाधान रनटाइम त्रुटि के कारण होगा क्योंकि जिन संख्याओं में दशमलव भाग होता है वे कभी भी 0 को कम नहीं कर पाएंगे।

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

समस्या मानक समस्याओं में से एक है, जिसे बहुत व्यापक रूप से जाना जाता है। समस्या को आसानी से हल किया जा सकता है अगर हम 1 को घटाते हैं जब हम एक विषम संख्या का सामना करते हैं। और संख्या को 2 से विभाजित करें, जब हम एक समान संख्या प्राप्त करते हैं। इस प्रकार समस्या का समाधान पूर्णांक की समता पर निर्भर है। जब संख्या समान है तो हम 2 से क्यों विभाजित करते हैं? क्योंकि संख्या को घटाकर घटाकर आधा करना हमेशा बेहतर या समान रूप से ठीक होता है। 1. फिर हम विषम संख्याओं को विभाजित क्यों नहीं करते? क्योंकि तब हम दशमलव पूर्णांकों को समाप्त कर देंगे, जिसे किसी भी तरह से इन दो कार्यों का उपयोग करके 0 तक कम नहीं किया जा सकता है।

शून्य लिटकोड समाधान के लिए एक संख्या को कम करने के लिए कदमों की संख्या के लिए अनुकूलित कोड

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), जब भी हम पूर्णांक को 2 से विभाजित करते हैं जब भी हमें एक सम संख्या मिलती है। प्रत्येक विषम संख्या को फिर 1 से घटाकर भी संख्या में बदल दिया जाता है। इस प्रकार समय जटिलता लॉगरिदमिक के रूप में सामने आती है।

अंतरिक्ष जटिलता

ओ (1), क्योंकि हमने एक एकल चर का उपयोग किया है, जो कि निरंतर स्थान है। इस प्रकार अंतरिक्ष जटिलता भी स्थिर है।