# Daily Coding Challenge #71

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;
}
};


/*

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!

## wingkwong / atcoder

Posted on by:

### Wing-Kam

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