Број на чекори за да се намали бројот до решението за нулта код


Ниво на тешкотија Лесно
Често прашувано во Амазон Google ХРТ Мајкрософт
Манипулација со малку

Проблемот Број на чекори за намалување на број до нула решение за леткод го наведува оној што е даден број. Пронајдете минимален број чекори за да го претворите дадениот цел број во 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), затоа што користевме единствена променлива, тоа е постојан простор. Така, вселенската комплексност е исто така постојана.