Hey folks

My friend shared a question asked to him in a MAANG interview:

You are given a Binary tree, each of the nodes of the tree is coloured with a colour belonging to {R, G, B}. You have to find all possible root nodes of the tree s.t. any path from the root to any node follows the colour pattern of R -> G -> B -> R -> G -> B -> R -> .... It need not start from R, it can start from any colour but needs to follow the RGB pattern cyclically.

My Solution:

My first observation is that: there can only be a single node that can be a root of such a tree. We can prove this by saying if there are two such nodes (let's say A and B), then the path from A to B follows the RGB pattern as well as the path from B to A, which is not possible; hence, there can only be a single root following the constraints.

My other observation is: If we choose some other node as root (than the one that follows the constraints), if we go down; path along one of the child will follow RGB pattern and the one along other child (this one has our answer root in its subtree) will follow BGR pattern (basically reverse of RGB). So the one that follows the BGR pattern will at some point reach our actual root node, and from that point onwards, the BGR pattern reverses to the RGB pattern. So basically, we look for this reversal point and this will only be our candidate answer.

Hence, we just verify if our candidate follows the constraints.

I'm not able to find this problem anywhere online. I found the problem quite interesting and hence am sharing here. But more importantly, I want to know if my solution is correct or not?

UPDATE:

kr25161 suggested an alternative solution, which I like even more:

"simultaneously you can say, if any node u is S[i] and all of its neigbours are S[(i + 1) % 3] where S = "RGB", you can check for u if it satifies in O(n). if it doesnt you return false instantly after the check. because any node apart from u cannot be root for this tree."

I am trying to solve this problem, facing probably an overflow issue.

Here's my code:

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define NL cout<<"\n";

typedef long long int lli;

void Solve(){
	lli w, h, n; cin >> w >> h >> n;
	lli l=1, r = (sqrt(n)+1)*(max(w,h)), mid;
	while (l + 1 < r) {
		mid = l + (r-l)/2;
		if ((mid/w) *(mid/h) > n) {
			r = mid;
		} else {
			l = mid;
		}
	}
	// cout << l << ", " << r;NL
	if ((l/w)*(l/h) == n) {
		cout << l;NL;
	} else {
		cout << r;NL;
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	lli t;
	// cin >> t;
	t=1;
	for (int i=0; i<t; ++i) { Solve();}
	return 0;
}

I am sure there's an overflow issue but I have one more doubt. After being unsuccessful after many attempts, I started reading comments under the problems and found a guy who posted his working solution as:

#include<bits/stdc++.h>
#define ll long long

using namespace std;
int main(){
	unsigned ll a, b, n;
	cin >> a >> b >> n;
	unsigned ll l = 0, r = 1e18;

	while(r > l+1){

		unsigned ll m = (l+r)/2;
		if((m/a)*(m/b) >= n){
			r = m;
		}
		else l = m;
	}
	cout << r;
}

I read his code and found he didn't do anything for the overflow issue except use an unsigned data type. I submitted his code just to see if it works but it failed in the $$$27^{th}$$$ test case (Mine was failing in the $$$5^{th}$$$ test case). So I thought I should try my code with unsigned long long, and therefore I did, here's the code:

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define NL cout<<"\n";

#define ll long long

void Solve(){
	unsigned ll w, h, n; cin >> w >> h >> n;
	unsigned ll l=0, r = 1e18, mid;
	while (l + 1 < r) {
		mid = l + (r-l)/2;
		if ((mid/w) *(mid/h) > n) {
			r = mid;
		} else {
			l = mid;
		}
	}
	// cout << l << ", " << r;NL
	if ((l/w)*(l/h) >= n) {
		cout << l;NL;
	} else {
		cout << r;NL;
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll t;
	// cin >> t;
	t=1;
	for (int i=0; i<t; ++i) { Solve();}
	return 0;
}

But still my code failed on $$$5^{th}$$$ test case only. That makes me doubt my binary search algorithm.

I have tried to maintain the following invariants: $$$f(l) \lt = n$$$, and $$$f(r) \gt n$$$, throughout the binary search loop, and then at the end I check if $$$f(l) == n$$$ or not if yes then return $$$l$$$ otherwise $$$r$$$.

I have also tried using double, and using logarithms for the comparison but it didn't work. I tried $$$ log(\frac{mid}{w}) + log(\frac{mid}{h}) \gt log(n) $$$, don't know why this shouldn't work, would appreciate your views on this.

Please have a look at my binary search algo and see if it is correct. Also, it would be great if you give me some hint on how to avoid overflow. I have really spent a lot of time on this problem (which is very straightforward except for the overflow part), so your help would be really appreciated.

Thanks a lot! May you have a wonderful day!