صفر ليٽ ڪوڊ جو حل نمبر گھڻڻ جو مرحلو


تڪليف جي سطح آسان
بار بار پڇڻ ۾ Amazon گوگل اي آر ٽي Microsoft جي
بٽ مينپوليشن

زيرو ليٽ ڪوڊ جو ڪو نمبر گهٽائڻ لاءِ قدمن جو مسئلو لکي ٿو ته ڏنو ويو آهي انٽرويو. ڏنل عدد کي 0 ۾ تبديل ڪرڻ لاءِ گهٽ ۾ گهٽ مرحلن کي ڳوليو. توهان ٻن مرحلن کي انجام ڏئي سگهو ٿا ، يا ته 1 کي ٽوڙيو يا انٽيگر کي 2 ذريعي ورهائي. مسئلو سادو لڳي ٿو پر حل ذريعي وڃڻ کان پهريان ، اسان ڪجهه مثال ڏسندا. .

صفر ليٽ ڪوڊ جو حل نمبر گھڻڻ جو مرحلو

n = 14
6

وضاحت: ڏنل عدد کي گھٽائڻ لاءِ گهٽ ۾ گهٽ تعداد (= 14) 0 کي 6 قدمن جي ضرورت آهي. پهريون ، 14 کي 2 سان ورهايو. هاڻ اسان 7. سان گڏ رهجي ويا آهيون. پوءِ اسان 1 کي ڇڏيو. اسان جو نمبر هاڻي آهي 6. اسان ٻيهر 2 سان ورهايو ٿا. پوءِ اسان 1 کي 3 ڀيرا گهٽائي ڇڏيو عدد (= 0) کي XNUMX ۾ گهٽائڻ لاءِ.

8
4

وضاحت: اسان 3 ڊيوڊ کي گهٽائڻ لاءِ 1 ڊويزن ۽ 8 گهٽائڻ وارو آپريشن استعمال ڪريون ٿا پهرين هلڻ 0 کي 8 کي گهٽائي ٿي ، پوءِ 4 کي 4 ، 2 کي 2 کي. پوءِ اسان 1 مان حاصل ڪرڻ لاءِ 1 مان 1 کي گهٽائي ڇڏيو.

زيرو ليٽ ڪوڊ جو تعداد گھٽائڻ جي قدمن جي تعداد ۾ بروٿ فورس قدم

مسئلو ڪافي معياري آهي ۽ ڪيترن ئي تجربن ۾ ڪيترائي ڀيرا پڇيو ويو آهي. مسئلي جي حل لاءِ بروقت قوت وارو حل وقت جي حد ھيٺ ڪافي نه آھي. برٽسٽ فورس حل جي حل لاءِ تاليف استعمال ڪندي آهي. هر انٽيگر لاءِ ، جتان اسان وٽ ٻه ممڪن آپريشن آهن. اسان انهن ٻنهي کي انجام ڏيو ۽ پوءِ سڌاريل سان عدل واري انڊيگر لاءِ سڏيون ٿا. حل لاءِ وقت جي پيچيدگي فوري طور تي موثر ثابت ٿيندي ۽ وڏي آمدن لاءِ ڪارائتو ناهي. حل جڏهن ڪوڊ ڪيو ويندو رن ٽائيم جي غلطي جو نتيجو ٿيندو ڇاڪاڻ ته نمبرن ۾ جيڪي ڊيمل حصو هوندا آهن ڪڏهن به 0 کي گهٽ ڪرڻ جي قابل نه هوندا.

زيرو ليٽ ڪوڊ جو حل نمبر گهٽائڻ لاءِ قدمن جي تعداد لاءِ اصلاح وارو نقشو

مسئلو معياري مسئلن مان هڪ آهي ، جيڪي تمام وڏا knownاتل آهن. مسئلو اسان کي آسانيءَ سان حل ڪري سگھون ٿا جيڪڏهن اسان فقط 1 کي ٽوڙيون جڏهن اسان هڪ بي جوڙ نمبر سان منهن ڏيون ٿا. ۽ 2 کي عدد کان ورهايو ، جڏهن ته اسان کي به هڪ نمبر ملي. اھڙي طرح مسئلي جو حل انٽيگر جي برابري تي منحصر آھي. جڏهن نمبر به آهي ته 2 کان ڌار ڇو ڪريون ٿا؟ ڇاڪاڻ ته اهو نمبر گهٽائڻ لاءِ اهو هميشه بهتر يا برابر آهي ـ گهٽائڻ بجاءِ 1 کي گهٽائڻ جي ، ان ڪري اسان ڇو نٿا مسڪن نمبرن کي ورهايو؟ ڇاڪاڻ ته پوءِ اسان ختم ٿيڻ وارا عددي عدد هجڻ گهرجي ، جيڪي ڪنهن به طريقي سان انهن ٻن عملن کي استعمال ڪندي 0 ۾ گهٽجي نٿا سگهن.

صفر ليٽ ڪوڊ جو ڪو نمبر گھٽائڻ جي مرحلن جي عدد لاءِ بهتر ڪوڊ

سي ++ ڪوڊ

#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) ، ڇاڪاڻ ته اسان هڪ ئي متغير استعمال ڪيو ، اهو مسلسل جڳهه آهي. ان ڪري خلاءَ جي پيچيدگي پڻ مستقل آهي.