पाण्याचे बाटल्या लीटकोड सोल्यूशन


अडचण पातळी सोपे
वारंवार विचारले मायक्रोसॉफ्ट
लोभी

समस्या विधान

“वॉटर बॉटल” या समस्येमध्ये आम्हाला “नंबबॉटल” अशी दोन मूल्ये दिली आहेत जी संपूर्ण पाण्याच्या बाटल्या आणि “नेमएक्सचेंज” ची एकूण संख्या साठवून ठेवेल जी आम्ही एकाच वेळी विनिमय करू शकणार्‍या रिकाम्या बाटल्यांची एकूण संख्या साठवून ठेवेल. पाण्याची बाटली.

पूर्ण पाण्याच्या बाटलीमधून पाणी पिल्यानंतर ते रिकाम्या पाण्याच्या बाटलीत बदलते. आमचे कार्य म्हणजे आम्ही पिऊ शकू शकू अशा पाण्याच्या जास्तीत जास्त पाण्याच्या बाटल्या शोधणे.

उदाहरण

numBottles = 15, numExchange = 4
19

स्पष्टीकरण:

पाण्याचे बाटल्या लीटकोड सोल्यूशन

पहिली फेरी: पेय 15 पाण्याच्या बाटल्या 15 रिकाम्या बाटल्या देतात.

दुसरी फेरी: या 15 पाण्याच्या बाटल्यांमधून आम्हाला पाण्याच्या 3 पूर्ण बाटल्या मिळतात आणि 3 रिकाम्या बाटल्या सोडल्या. पेय 3 आम्ही आता एकूण 6 रिकाम्या बाटल्या सोडल्या.

तिसरी फेरी: या 6 पाण्याच्या बाटल्यांमधून आम्हाला 1 पाण्याची पूर्ण बाटली मिळते आणि 2 रिकाम्या बाटल्या सोडल्या. आम्ही आता एकूण 1 रिकाम्या बाटल्या सोडल्या आहेत.

कमीतकमी 4 बाटल्यांची बाटली बदलण्यासाठी आवश्यक असल्याने आम्ही आता पूर्ण पाण्याची बाटली विकत घेऊ शकत नाही. म्हणून आम्ही पिऊ शकू शकू अशा पाण्याच्या बाटल्यांची जास्तीत जास्त संख्या 15 + 3 + 1 = 19.

पाण्याच्या बाटल्या लीटकोड सोल्यूशनसाठी दृष्टीकोन

समस्येचे निराकरण करण्याचा मूळ दृष्टीकोन म्हणजे प्रश्न जे विचारतात ते करणे.

  1. सर्व पाण्याच्या बाटल्या प्या आणि नंतर ते रिकाम्या पाण्याच्या बाटल्यांमध्ये रुपांतरीत होते.
  2. सर्व रिकाम्या पाण्याच्या बाटल्यांमधून पाण्याच्या पूर्ण बाटल्या खरेदी करतात.
  3. आम्ही रिकाम्या पाण्याच्या बाटलीतून पाण्याची पूर्ण बाटली खरेदी करू शकत नाही तोपर्यंत या चरणांची पुनरावृत्ती करा.
  4. प्रक्रियेदरम्यान आम्ही प्यालेल्या पाण्याच्या एकूण बाटल्यांची एकूण संख्या परत करा.

आम्ही सुधारू शकतो गुंतागुंत काही निरीक्षणे करून समाधानाचे:

  1. आमच्याकडे पाण्याच्या पूर्ण बाटल्यांची नंबरबोटल संख्या आहे म्हणून आम्ही पिण्याच्या पाण्याच्या बाटल्यांची ही किमान संख्या असेल.
  2. 1 पूर्ण पाण्याची बाटली = 1 युनिट पाणी + 1 रिकामी पाण्याची बाटली.
  3. नंबर एक्सचेंज रिकाम्या पाण्याच्या बाटल्यांमधून आम्हाला 1 पूर्ण पाण्याची बाटली (1 युनिट वॉटर + 1 रिकामी पाण्याची बाटली) मिळते. या गोष्टीचे स्पष्टीकरण (numExchange-1) पाण्याच्या बाटल्यांना 1 युनिट पाणी देखील दिले जाऊ शकते.
  4. परंतु जर शेवटच्या फेरीत आमच्याकडे (numExchange-1) रिक्त बाटल्या असतील तर आम्हाला एक युनिट पाणी मिळू शकत नाही.
  5. तर आमचा निकाल numbટલ + (numBટલ / (numExchange -1)) असेल आणि numbટલ% (numExchange -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) कारण आम्ही उत्तर संग्रहित करण्यासाठी फक्त एक व्हेरिएबल वापरत आहोत.

संदर्भ