Решење са флашицама за воду


Ниво тешкоће Лако
Често питани у мицрософт
Похлепан

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

У проблему „Боце за воду“ дате су нам две вредности, наиме „нумБоттле“ која ће сачувати укупан број пуних боца воде и „нумЕкцханге“ која ће сачувати укупан број празних боца воде које истовремено можемо разменити и добити пуну боца за воду.

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

Пример

numBottles = 15, numExchange = 4
19

objašnjenje:

Решење са флашицама за воду

Први круг: пити 15 боце воде даје 15 празних боца.

Друга рунда: од ових 15 боца воде добијамо 3 пуне боце воде, а са 3 празне боце. Пиће 3 флаше са водом сада смо оставили са укупно 6 празних боца.

Трећи круг: од ових 6 боца воде добијамо 1 пуну боцу воде, а са 2 празне боце. Попијте 1 боцу воде коју смо сада оставили са укупно 3 празне боце.

Како су за замену боце потребне најмање 4 боце, више не можемо купити пуну боцу воде. Дакле, максималан број флаша са водом који можемо да пијемо је 15 + 3 + 1 = 19.

Приступ за решење флашица са флашама за воду

Основни приступ решавању проблема је радити оно што постављају питања.

  1. Попијте све пуне боце воде, а затим се претворе у празне боце воде.
  2. Од свих празних боца за воду купите пуне боце за воду.
  3. Понављајте ове кораке све док из празне боце не можемо купити пуну боцу воде.
  4. Вратите укупан број пуних боца воде које смо попили током процеса.

Можемо побољшати сложеност решења изношењем неколико запажања:

  1. Имамо нумБоттле број пуних боца воде, тако да ће ово бити минимални број пуних боца воде које можемо попити.
  2. 1 пуна боца воде = 1 јединица воде + 1 празна боца воде.
  3. Од празних боца за воду нумЕкцханге добијамо 1 пуну боцу воде (1 јединица воде + 1 празна боца воде). Ова ствар се такође може тумачити као (нумЕкцханге-1) боце с водом дају 1 јединицу воде.
  4. Али ако у последњем кругу ако имамо (нумЕкцханге-1) број празних боца, онда не можемо добити једну јединицу воде.
  5. Дакле, наш резултат ће бити нумБоттле + (нумБоттле / (нумЕкцханге -1)) и ако је нумБоттле% (нумЕкцханге -1) == 0 онда одузмите 1 од коначног одговора.

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

Ц ++ код за флаше са водом

#include <bits/stdc++.h> 
using namespace std; 
    int numWaterBottles(int numBottles, int numExchange) {
        int ans= numBottles + (numBottles) / (numExchange - 1);
        if((numBottles) %(numExchange - 1)==0)
            ans--;
        return ans;
    }
int main() 
{ 
 int numBottles = 15, numExchange = 4;
 int ans=numWaterBottles(numBottles,numExchange);
 cout<<ans<<endl;
 return 0;
}
19

Јава код за флаше са водом

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
public class Tutorialcup {
    public static int numWaterBottles(int numBottles, int numExchange) {
        int ans= numBottles + (numBottles) / (numExchange - 1);
        if((numBottles) %(numExchange - 1)==0)
            ans--;
        return ans;
    }
  public static void main(String[] args) {
     int numBottles = 15, numExchange = 4;
     int ans=numWaterBottles(numBottles,numExchange); 
        System.out.println(ans);
  }
}
19

Анализа сложености решења за флаше са водом са флашама за воду

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

Временска сложеност горњег кода је О (1).

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

Сложеност простора горњег кода је О (1) јер користимо само променљиву за чување одговора.

Референце