loading...

Daily Coding Challenge #71

wingkwong profile image Wing-Kam 惻4 min read

About

This is a series of Daily Coding Challenge. Each day I show a few solutions written in C++. The questions are from coding practice/contest sites such as HackerRank, LeetCode, Codeforces, Atcoder and etc.


/*
LeetCode - Water Bottles

Given numBottles full water bottles, you can exchange numExchange empty water bottles for one full water bottle.

The operation of drinking a full water bottle turns it into an empty bottle.

Return the maximum number of water bottles you can drink.


Example 1:


Input: numBottles = 9, numExchange = 3
Output: 13
Explanation: You can exchange 3 empty bottles to get 1 full water bottle.
Number of water bottles you can drink: 9 + 3 + 1 = 13.
Example 2:


Input: numBottles = 15, numExchange = 4
Output: 19
Explanation: You can exchange 4 empty bottles to get 1 full water bottle. 
Number of water bottles you can drink: 15 + 3 + 1 = 19.
Example 3:

Input: numBottles = 5, numExchange = 5
Output: 6
Example 4:

Input: numBottles = 2, numExchange = 3
Output: 2


Constraints:

1 <= numBottles <= 100
2 <= numExchange <= 100
*/

class Solution {
public:
    int numWaterBottles(int numBottles, int numExchange) {
        // if numBottles < numExchange, numBottles is the ans
        int sum=numBottles; 
        while(numBottles>=numExchange){
            // find out how many full & empty bottles
            int full = numBottles/numExchange;
            int empty =numBottles%numExchange;
            // the new num of bottles = full bottles + empty bottles
            numBottles=full+empty;
            // add no. of full bottles to ans
            sum+=full;
        }
        return sum;
    }
};

/*
LeetCode - Number of Nodes in the Sub-Tree With the Same Label

Given a tree (i.e. a connected, undirected graph that has no cycles) consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges. The root of the tree is the node 0, and each node of the tree has a label which is a lower-case character given in the string labels (i.e. The node with the number i has the label labels[i]).

The edges array is given on the form edges[i] = [ai, bi], which means there is an edge between nodes ai and bi in the tree.

Return an array of size n where ans[i] is the number of nodes in the subtree of the ith node which have the same label as node i.

A subtree of a tree T is the tree consisting of a node in T and all of its descendant nodes.



Example 1:


Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], labels = "abaedcd"
Output: [2,1,1,1,1,1,1]
Explanation: Node 0 has label 'a' and its sub-tree has node 2 with label 'a' as well, thus the answer is 2. Notice that any node is part of its sub-tree.
Node 1 has a label 'b'. The sub-tree of node 1 contains nodes 1,4 and 5, as nodes 4 and 5 have different labels than node 1, the answer is just 1 (the node itself).
Example 2:


Input: n = 4, edges = [[0,1],[1,2],[0,3]], labels = "bbbb"
Output: [4,2,1,1]
Explanation: The sub-tree of node 2 contains only node 2, so the answer is 1.
The sub-tree of node 3 contains only node 3, so the answer is 1.
The sub-tree of node 1 contains nodes 1 and 2, both have label 'b', thus the answer is 2.
The sub-tree of node 0 contains nodes 0, 1, 2 and 3, all with label 'b', thus the answer is 4.
Example 3:


Input: n = 5, edges = [[0,1],[0,2],[1,3],[0,4]], labels = "aabab"
Output: [3,2,1,1,1]
Example 4:

Input: n = 6, edges = [[0,1],[0,2],[1,3],[3,4],[4,5]], labels = "cbabaa"
Output: [1,2,1,1,2,1]
Example 5:

Input: n = 7, edges = [[0,1],[1,2],[2,3],[3,4],[4,5],[5,6]], labels = "aaabaaa"
Output: [6,5,4,1,3,2,1]


Constraints:

1 <= n <= 10^5
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
ai != bi
labels.length == n
labels is consisting of only of lower-case English letters.
*/

class Solution {
public:
    vector<int> ans;
    vector<vector<int>> g;
    string l;
    int c[26]={};
    void dfs(int u=0, int p=-1){
        // lc is local count, add 1 before getting into the subtree
        int lc=c[l[u]-'a']++;
        for(int v:g[u]) {
            // perform dfs only if v is not same as parent
            if(v^p) dfs(v,u);
        }
        // ans[u] would be the current count - local count of u
        ans[u]=c[l[u]-'a']-lc;
    }

    vector<int> countSubTrees(int n, vector<vector<int>>&    edges, string labels) {
        ans.resize(n);
        g.resize(n);
        // passing labels to dfs would cause TLE
        l=labels;
        for(auto e:edges){
            g[e[0]].push_back(e[1]);
            g[e[1]].push_back(e[0]);
        }
        dfs();
        return ans;
    }
};

/*
LeetCode - Add Binary

Given two binary strings, return their sum (also a binary string).

The input strings are both non-empty and contains only characters 1 or 0.

Example 1:

Input: a = "11", b = "1"
Output: "100"
Example 2:

Input: a = "1010", b = "1011"
Output: "10101"


Constraints:

Each string consists only of '0' or '1' characters.
1 <= a.length, b.length <= 10^4
Each string is either "0" or doesn't contain any leading zero.
*/

class Solution {
public:
    string addBinary(string a, string b) {
        int i=a.size()-1, j=b.size()-1, c=0;
        string ans="";
        while(i>=0||j>=0||c==1){
            // add 1 to c if it is '1'
            c+=i>=0?a[i--]-'0':0;
            c+=j>=0?b[j--]-'0':0;
            // if both is 1, c&1 returns 0, else 1
            ans=to_string(c&1)+ans;
            // update c 
            c>>=1;
        }
        return ans;
    }
};

The source code is available in corresponding repo below. Star and watch for timely updates!

GitHub logo wingkwong / leetcode

šŸ† A Collection of my LeetCode Solutions with Explanations šŸ†

GitHub logo wingkwong / hackerrank

šŸ† A Collection of my HackerRank Solutions with Explanations šŸ†

GitHub logo wingkwong / codeforces

šŸ† A Collection of my Codeforces Solutions with Explanations šŸ†

GitHub logo wingkwong / atcoder

šŸ† A Collection of my AtCoder Solutions with Explanations šŸ†

Posted on by:

wingkwong profile

Wing-Kam

@wingkwong

Consultant by day. Developer by night. AWS certified. Exploring #CloudNative currently.

Discussion

markdown guide