נומער פון סטעפּס צו רעדוצירן אַ נומער צו נול לעעטקאָדע סאַלושאַן


שוועריקייט לעוועל גרינג
אָפט געבעטן אין אַמאַזאָן גוגל הרט מייקראָסאָפֿט
ביסל מאַניפּיאַליישאַן

די פּראָבלעם נומער פון סטעפּס צו רעדוצירן אַ נומער צו נול לעעטקאָדע סאַלושאַן שטאַטן אַז געגעבן אַן ינטעגער. געפֿינען די מינימום נומער פון סטעפּס צו בייַטן די געגעבן ינטאַדזשער צו 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. פארוואס טאָן ניט טיילן די מאָדנע נומערן? ווייַל מיר וועלן האָבן דעצימאַל גאַנץ נומערן וואָס קענען ניט זיין רידוסט צו 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

Java קאוד

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), ווייַל מיר געוויינט אַ איין בייַטעוודיק, דאָס איז קעסיידערדיק פּלאַץ. אזוי די פּלאַץ קאַמפּלעקסיטי איז אויך קעסיידערדיק.