नींबू पानी बदलें Leetcode Solution  


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना Atlassian
एल्गोरिदम कोडिंग लालची साक्षात्कार साक्षात्कार की तैयारी लेटकोड लेटकोड सॉल्यूशंस

यह पोस्ट लेमोनेड चेंज लेटकोड सॉल्यूशन पर है

समस्या का विवरण  

समस्या में "नींबू पानी बदलें" एक है पंक्ति ग्राहकों की। वे हमसे नींबू पानी खरीदना चाहते हैं जिसकी कीमत 5 रुपये है। ग्राहक हमें 5 रुपये, 10 रुपये या 20 रुपये दे सकते हैं। हम ग्राहकों को परिवर्तन की सही मात्रा वापस करना चाहते हैं। प्रारंभ में, हमारे पास कोई परिवर्तन नहीं है। हमें यह उत्तर देने की आवश्यकता है कि क्या हम प्रत्येक ग्राहक के लिए परिवर्तन की सही मात्रा को सफलतापूर्वक लौटा सकते हैं या नहीं।

उदाहरण  

 bills = [5,5,5,10,20]
true

स्पष्टीकरण:

नींबू पानी बदलें Leetcode Solutionपिन

शुरुआती तीन लेन-देन में, हमें कोई बदलाव करने की आवश्यकता नहीं है। तीन लेनदेन के बाद हमारे पास 5 रुपये के तीन सिक्के हैं। चौथे लेनदेन के दौरान, हमें 5 रुपये वापस करने की आवश्यकता है। इसलिए चौथे लेनदेन के बाद, हमारे पास 2 रुपये के 5 सिक्के और 10 रुपये के एक सिक्के हैं। पांचवें लेनदेन में, हमें 15 रुपये वापस करने की आवश्यकता है। हम एक दस रुपये का सिक्का और एक पांच रुपये का सिक्का वापस कर सकते हैं। चूंकि सभी लेनदेन पूरे हो चुके हैं, इसलिए उत्तर सही है।

दृष्टिकोण  

यह एक लालची एल्गोरिथ्म का उपयोग करके एक कार्यान्वयन समस्या है। जैसा कि ऐरे में दिए गए मान ग्राहकों की एक कतार का प्रतिनिधित्व करते हैं, इसलिए जब हम एरे को एक ही समय में बदलेंगे, तो हम लेनदेन भी करेंगे। प्रारंभ में, हमारे पास कोई परिवर्तन नहीं है इसलिए पाँच, दस और बीस रुपये के सिक्के शून्य हैं।

यह भी देखें
अनोखा पथ II

आइए प्रत्येक परिदृश्य को एक-एक करके देखें:

  1. यदि ग्राहक पांच रुपये का भुगतान करता है तो हमें उसे कोई बदलाव करने की आवश्यकता नहीं है और हमारे साथ पाँच रुपये के सिक्कों की संख्या में एक की वृद्धि होगी।
  2. मान लीजिए कि ग्राहक दस रुपये का भुगतान करता है, तो हमारे पास उसे बदलने के लिए कम से कम एक पाँच रुपये का सिक्का होना चाहिए। यदि हम ऐसा करने में विफल रहते हैं कि हम झूठे लौटेंगे क्योंकि सभी को परिवर्तन की सही मात्रा देना संभव नहीं है।
  3. यदि ग्राहक बीस रुपये का भुगतान करता है तो हम उसे दो अलग-अलग तरीकों से बदल सकते हैं:
    1. यदि हमारे पास दस रुपये का सिक्का और पाँच रुपये का सिक्का है तो हम उसे कुल पंद्रह रुपये वापस कर सकते हैं। यदि हम असफल होते हैं तो हम दूसरी विधि की तलाश करेंगे।
    2. चूँकि हमें कुल पंद्रह रुपये वापस करने हैं, इसलिए हम उसे पाँच रुपये के तीन सिक्के दे सकते हैं। इसके लिए हमारे पास फाइव रुपये के कम से कम 3 सिक्के होने चाहिए। यदि हम ऐसा करने में विफल रहते हैं कि हम झूठे लौटेंगे क्योंकि सभी को परिवर्तन की सही मात्रा देना संभव नहीं है।

यदि हमने सभी ग्राहकों को सही मात्रा में परिवर्तन प्रदान किया है तो हम केवल सही वापसी करेंगे।

कोड  

नींबू पानी बदलें Leetcode समाधान के लिए सी ++ कोड

#include <bits/stdc++.h> 
using namespace std; 
       bool lemonadeChange(vector<int>& bills) {
        int n=bills.size();
        int five=0,ten=0,twenty=0;
        for(int i=0;i<n;i++)
        {
            if(bills[i]==5)five++;
            else if(bills[i]==10)
            {
                ten++;
                if(five>0)five--;
                else return false;
            }   
            else 
            {
               twenty++;
                if(ten>0&&five>0){ten--;five--;}
                else if(five>2)five=five-3;
                else return false;
            }
                
        }
            return true;
    }

int main() 
{ 
 vector<int> arr = {5,5,5,10,20}; 
 cout <<boolalpha;
 cout<<lemonadeChange(arr)<<endl; 
 return 0;
}

 

true

नींबू पानी बदलें Leetcode समाधान के लिए जावा कोड

import java.util.Arrays; 
public class Tutorialcup {
    public static boolean lemonadeChange(int[] bills) {
                int n=bills.length;
        int five=0,ten=0,twenty=0;
        for(int i=0;i<n;i++)
        {
            if(bills[i]==5)five++;
            else if(bills[i]==10)
            {
                ten++;
                if(five>0)five--;
                else return false;
            }   
            else 
            {
               twenty++;
                if(ten>0&&five>0){ten--;five--;}
                else if(five>2)five=five-3;
                else return false;
            }
                
        }
            return true;
    }
  public static void main(String[] args) {
    int [] arr = {5,5,5,10,20}; 
    boolean ans= lemonadeChange(arr);
    System.out.println(ans);
  }
true

नींबू पानी बदलें Leetcode समाधान की जटिलता विश्लेषण  

समय की जटिलता

उपरोक्त कोड की समय जटिलता है पर) क्योंकि हम बिल सरणी को केवल एक बार ट्रेस कर रहे हैं। यहाँ n बिल सरणी की लंबाई है।

यह भी देखें
लेटकोड क्रमपरिवर्तन

अंतरिक्ष की जटिलता

उपरोक्त कोड की अंतरिक्ष जटिलता है ओ (1) क्योंकि हम उत्तरों को संग्रहीत करने के लिए केवल एक चर का उपयोग कर रहे हैं।

संदर्भ