Плус Оне Леетцоде решење


Ниво тешкоће Лако
Често питани у адобе амазонка јабука Цапитал Оне фацебоок гоогле мицрософт
Ред

Изјава о проблему

У задатку „Плус један“ добијамо низ где сваки елемент у низу представља цифру броја. Комплетни низ представља број. Нулти индекс представља МСБ броја. Можемо претпоставити да у броју нема водећу нулу.

Наш задатак је да додамо плус један задати број, а затим вратимо резултат у облику низа.

Пример

digits =[4,3,2,1]
[4,3,2,2]

objašnjenje:

Плус Оне Леетцоде решење

Као у датом примеру, низ представља 4321 и 4321 + 1 постаје 4322. Тако смо вратили 4322.

Приступ за решење Плус Оне Леетцоде

Прва идеја која свима падне на памет је претворити дати низ у број, извршити операцију сабирања, а затим вратити резултат у облику низа.

Али ова идеја неће успети за низ великих величина, јер се не би уклопила ни у један тип података.

Дакле, треба да обрадимо сваку цифру једну по једну.

  1. Почните од ЛСБ, а затим обрадите сваку цифру до МСБ.
  2. Ако је тренутна цифра мања од 9, додајте једну тренутној цифри и вратите низ који тренутно додељује нулу тренутној цифри.
  3. Ако је последњи елемент обрађен и такође је био једнак 9, то значи да су све цифре биле 9. Дакле, повећаћемо величину низа за један и доделити 1 МСБ-у.
  4. Врати низ

Имплементација

Ц ++ код за Плус Оне

#include <bits/stdc++.h> 
using namespace std; 
    vector<int> plusOne(vector<int>& digits) {
        int n=digits.size();
        for(int i=n-1;i>=0;i--)
        {
            if(digits[i]<9)
            {digits[i]++ ; return digits;} 
            else
                digits[i]=0;
        }
        vector<int>newnumber(n+1,0);
        newnumber[0]=1;
        return newnumber;
    }
int main() 
{ 
 vector<int> arr = {4,3,2,1}; 
  vector<int>ans= plusOne(arr); 
 for(int i=0;i<arr.size();i++)
 cout<<ans[i]<<" ";
 cout<<endl;
 return 0;
}
[4,3,2,2]

Јава код за Плус Оне

import java.util.Arrays; 
public class Tutorialcup {
public static int[] plusOne(int[] digits) {
        
    int n = digits.length;
    for(int i=n-1; i>=0; i--) {
        if(digits[i] < 9) {
            digits[i]++; return digits;
        }
        digits[i] = 0;
    }
    
    int[] newNumber = new int [n+1];
    newNumber[0] = 1;
    return newNumber;
}
  public static void main(String[] args) {
        int [] arr = {4,3,2,1}; 
        int[]ans=plusOne(arr); 
        System.out.println(Arrays.toString(ans));
  }
}
[4,3,2,2]

Анализа сложености решења Плус Оне Леетцоде

Временска сложеност

Временска сложеност горњег кода је Он) јер само једном прелазимо низом цифара. Овде је н дужина цифреног низа.

Свемирска сложеност

Сложеност простора горњег кода је О (1)  у случају да низ садржи бар једну цифру мању од 9, у супротном Он).

Референце