زیرو لیٹ کوڈ حل کی تعداد کو کم کرنے کے لئے اقدامات کی تعداد


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے ایمیزون گوگل HRT مائیکروسافٹ
بٹ ہیرا پھیری

زیرو لِٹ کوڈ حل کی تعداد کو کم کرنے کے لئے اقدامات کی دشواری عددی. دیئے گئے عدد کو 0 میں تبدیل کرنے کے ل steps کم سے کم اقدامات کی تلاش کریں۔ آپ دونوں میں سے کسی ایک کو بھی انجام دے سکتے ہیں ، یا تو 1 کو گھٹائیں یا عدد کو 2 سے تقسیم کریں۔ مسئلہ آسان لگتا ہے لیکن حل سے گزرنے سے پہلے ، ہم کچھ مثالوں دیکھیں گے .

زیرو لیٹ کوڈ حل کی تعداد کو کم کرنے کے لئے اقدامات کی تعداد

n = 14
6

وضاحت: دیئے گئے عدد (= 14) کو کم کرنے کے ل to کم سے کم مراحل میں 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 سے XNUMX کو گھٹاتے ہیں۔

زیرو لیٹ کوڈ حل میں تعداد کو کم کرنے کے لئے بروٹ فورس نقطہ نظر

مسئلہ کافی معیاری ہے اور متعدد بار مختلف ٹیسٹوں میں پوچھا گیا ہے۔ مسئلے کا بروٹ فورس حل وقت کی حد کے تحت مسئلہ حل کرنے کے لئے کافی نہیں ہے۔ بروٹ فورس حل حل کے لئے تکرار کا استعمال کرتا ہے۔ ہر ایک عدد کے ل، ، چونکہ ہمارے پاس دو ممکنہ آپریشن ہیں۔ ہم ان دونوں کو انجام دیتے ہیں اور پھر بار بار ترمیم شدہ عدد کو طلب کرتے ہیں۔ حل کے ل complex وقت کی پیچیدگی قابل تعزیر ہوگی اس طرح بڑی معلومات کے ل in موثر نہیں ہے۔ کوڈڈ ہونے پر حل رن ٹائم غلطی کا سبب بنے گا کیونکہ اعداد جس میں اعشاریے پر مشتمل ہوتا ہے وہ کبھی 0 تک کم نہیں ہوسکے گا۔

زیرو لیٹ کوڈ حل کی تعداد کو کم کرنے کے لئے اقدامات کی تعداد کے ل Op آپ Approڈائزڈ اپروچ

مسئلہ ایک معیاری مسئلہ ہے ، جو بہت وسیع پیمانے پر جانا جاتا ہے۔ اس مسئلے کو آسانی سے حل کیا جاسکتا ہے جب ہم صرف 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 کو گھٹاتے ہوئے مساوی تعداد میں تبدیل کیا جاتا ہے۔ اس طرح وقت کی پیچیدگی لاجارتھمک بن کر سامنے آتی ہے۔

خلائی پیچیدگی

O (1) ، کیونکہ ہم نے ایک متغیر کا استعمال کیا ، وہ مستقل جگہ ہے۔ اس طرح جگہ کی پیچیدگی بھی مستقل ہے۔