Landline Infrastructure

Easy

0/40

1 upvote

Problem statement

You are tasked with planning the landline infrastructure for m houses across n new colonies. The connection plan is as follows: within each colony, every house must be connected by a landline to every other house in that same colony. There are no connections between different colonies.

You must assign each of the m houses to one of the n colonies. A key constraint is that every colony must have at least one house. Your goal is to find the minimum and maximum possible number of total landline connections required across all colonies, depending on how you distribute the houses.

Return an array (or pair) of size 2, containing the minimum possible connections at index 0 and the maximum possible connections at index 1

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer m, the total number of houses.
The second line contains an integer n, the total number of colonies.

Output Format:

The output should be two space-separated long integers: the minimum possible connections and the maximum possible connections.

Note:

If a colony has h houses, the number of connections required within that colony is h * (h - 1) / 2.
The total number of connections is the sum of connections from all n colonies.
You must find two arrangements: one that minimizes this total sum, and one that maximizes it.

Sample Input 1:

8
3

Sample Output 1:

7 15

Explanation for Sample 1:

We have 8 houses to distribute among 3 colonies.
  To Minimize Connections: We distribute the houses as evenly as possible: [3, 3, 2].
    Colony 1 (3 houses): 3 * 2 / 2 = 3 connections.
    Colony 2 (3 houses): 3 * 2 / 2 = 3 connections.
    Colony 3 (2 houses): 2 * 1 / 2 = 1 connection.
  Minimum Total = 3 + 3 + 1 = 7.
  To Maximize Connections: We make one colony as large as possible and the others as small as possible (with a minimum of 1 house each). The distribution is [1, 1, 6].
    Colony 1 (1 house): 1 * 0 / 2 = 0 connections.
    Colony 2 (1 house): 1 * 0 / 2 = 0 connections.
    Colony 3 (6 houses): 6 * 5 / 2 = 15 connections.
  Maximum Total = 0 + 0 + 15 = 15.

Expected Time Complexity:

The expected time complexity is O(1).

Constraints:

1 <= n <= m <= 10000

Approaches (1)

Approach 1

Optimized Approach

Time Complexity

Space Complexity

(100% EXP penalty)

Landline Infrastructure

Console