DEV Community: Siddhesh Bhupendra Kuakde

1518. Water Bottles || LeetCode || C++

Siddhesh Bhupendra Kuakde — Wed, 01 Oct 2025 04:25:04 +0000

1518. Water Bottles || LeetCode || C++

Solving LeetCode problem 1518. Water Bottles with a simple greedy approach in C++.

Intuition

We are given a number of full bottles and a rule that allows exchanging empty bottles for new full ones.

At first glance, this is similar to repeatedly trading resources:

every time we have enough empty bottles, we can exchange them for more full bottles.

The total number of bottles consumed will be the sum of:

Initially available bottles
Plus all future bottles obtained by exchanges.

Approach

Start with numBottles full bottles, so the total consumed begins at numBottles.
After drinking them, we gain the same number of empty bottles.
While the number of empty bottles is greater than or equal to numExchange:
- Exchange as many as possible: t = numBottles / numExchange (new bottles obtained).
- Add t to the total consumed count.
- Compute the remaining bottles after exchange: rem = numBottles % numExchange.
- The new count of empty bottles becomes t + rem.
Repeat until exchanges are no longer possible.
Return the total consumed.

This greedy approach works because each exchange step maximizes the number of bottles we can drink at that stage.

Complexity

Time complexity:

Each loop iteration reduces the number of bottles by at least 1, so the loop runs at most O(numBottles) times.

Effectively, the complexity is closer to O(log(numBottles)) since bottles shrink quickly with division.
Space complexity:

We only use a few extra variables (t, rem, numOfBottles), so the space usage is O(1).

Code (C++)


cpp
class Solution {
public:
    int numWaterBottles(int numBottles, int numExchange) {
        int numOfBottles = numBottles;

        while (numBottles >= numExchange) {
            int t = numBottles / numExchange; // number of new bottles obtained
            int rem = numBottles % numExchange; // leftover bottles
            numOfBottles += t;
            numBottles = t + rem; // update for next round
        }

        return numOfBottles;
    }
};

Subsets

Siddhesh Bhupendra Kuakde — Mon, 15 Sep 2025 03:45:22 +0000

Iterative:

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> ans;
        ans.push_back({});
        for (int num : nums) {
            int size = ans.size();

            for(int i=0; i<size; i++){ // size 1 so fill all once time
                vector<int> ss = ans[i]; // just take current and more to it as per previous size 
                ss.push_back(num); // 1 -> 1 ,
                for(int i=0; i<ss.size(); i++){
                    cout<<ss[i];
                } 
                cout<<endl; 
                ans.push_back(ss);
            }
        }
// [] [0] [1] [2] [0 ,1] [1,2] [2 ,3] 
// 
        return ans;
    }
};

Recursive

class Solution {
public:
    void createSubset(vector<int>& nums, int index , vector<vector<int>>&res, vector<int>&subset ){
        if(index == nums.size())
        {
            res.push_back(subset);
            return; 
        }
        subset.push_back(nums[index]); // take current 
        createSubset(nums, index+1, res, subset);

        subset.pop_back(); // dont take current 
        createSubset(nums, index+1, res, subset);

    }
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res; 
        vector<int> subset;
        createSubset(nums, 0 , res, subset);
        return res; 
    }
     vector<vector<int>> subsets2(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> ans;
        ans.push_back({});
        for (int num : nums) {
            int size = ans.size();

            for(int i=0; i<size; i++){ // size 1 so fill all once time
                vector<int> ss = ans[i]; // just take current and more to it as per previous size 
                ss.push_back(num); // 1 -> 1 ,
                for(int i=0; i<ss.size(); i++){
                    cout<<ss[i];
                } 
                cout<<endl; 
                ans.push_back(ss);
            }
        }
// [] [0] [1] [2] [0 ,1] [1,2] [2 ,3] 
// 
        return ans;
    }
};

1935. Maximum Number of Words You Can Type |

Siddhesh Bhupendra Kuakde — Mon, 15 Sep 2025 03:08:49 +0000

Intuition

Given string some char broken they cant be used to make that word. return the miniumum number of words that we can form with this.

Approach

just check and reduce the count if the chars are found

Complexity

Time complexity:
O arr size and O borken letter size
Space complexity:
On for array

Code

```cpp []
class Solution {
public:
int canBeTypedWords(string text, string brokenLetters) {

    // Hello world ad  
    stringstream ss(text);
    vector<string> arr; 
    string word;    
    while(ss >> word){
        arr.push_back(word);
    }
    int ans = arr.size(); 
    for(string  s: arr){

        for(int i=0; i<brokenLetters.size(); i++){
            if(s.contains(brokenLetters[i])){ 
               --ans; break;
            }
        }

    }
    return ans; 
}

};