Answer: Infosys | OA | Coding Round | Space X - The Oracle of Eldoria

Problem Solution The Mathematical Strategy 1. Identifying the Realms When the bridges broke, the kingdom was partitioned into M disjoint connected components (K1​,K2​,…,KM​). If you pick any non-empty subset of cities from a single isolated region Ki​, they will still form exactly one connected realm (assuming the internal connectivity of that region remains). Therefore, to form exactly X isolated realms, you must pick at least one city from exactly X different initial regions. 2. Counting Ways for a Single Region ...