Skip to content

3200. Maximum Height of a Triangle

Description

You are given two integers red and blue representing the count of red and blue colored balls. You have to arrange these balls to form a triangle such that the 1st row will have 1 ball, the 2nd row will have 2 balls, the 3rd row will have 3 balls, and so on.

All the balls in a particular row should be the same color, and adjacent rows should have different colors.

Return the maximum height of the triangle that can be achieved.

 

Example 1:

Input: red = 2, blue = 4

Output: 3

Explanation:

The only possible arrangement is shown above.

Example 2:

Input: red = 2, blue = 1

Output: 2

Explanation:


The only possible arrangement is shown above.

Example 3:

Input: red = 1, blue = 1

Output: 1

Example 4:

Input: red = 10, blue = 1

Output: 2

Explanation:


The only possible arrangement is shown above.

 

Constraints:

  • 1 <= red, blue <= 100

Solutions

Solution 1: Simulation

Thinking

A triangle of height \(h\) uses \(h(h+1)/2\) balls, so \(h\) is at most \(O(\sqrt{\textit{red}+\textit{blue}})\). With \(1\le \textit{red},\textit{blue}\le 100\) we could enumerate heights and row colors, yet adjacent rows must differ, so the whole coloring is fixed once the first row is chosen.

It therefore suffices to try red-first and blue-first, then subtract \(1,2,\ldots\) balls from the two colors in alternation. Stop when the next row exceeds the remaining count of that color, and keep the larger feasible height. Flipping the color index by XOR keeps the simulation in constant extra space.

We can enumerate the color of the first row, then simulate the construction of the triangle, calculating the maximum height.

The time complexity is \(O(\sqrt{n})\), where \(n\) is the number of red and blue balls. The space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def maxHeightOfTriangle(self, red: int, blue: int) -> int:
        ans = 0
        for k in range(2):
            c = [red, blue]
            i, j = 1, k
            while i <= c[j]:
                c[j] -= i
                j ^= 1
                ans = max(ans, i)
                i += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public int maxHeightOfTriangle(int red, int blue) {
        int ans = 0;
        for (int k = 0; k < 2; ++k) {
            int[] c = {red, blue};
            for (int i = 1, j = k; i <= c[j]; j ^= 1, ++i) {
                c[j] -= i;
                ans = Math.max(ans, i);
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    int maxHeightOfTriangle(int red, int blue) {
        int ans = 0;
        for (int k = 0; k < 2; ++k) {
            int c[2] = {red, blue};
            for (int i = 1, j = k; i <= c[j]; j ^= 1, ++i) {
                c[j] -= i;
                ans = max(ans, i);
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func maxHeightOfTriangle(red int, blue int) (ans int) {
    for k := 0; k < 2; k++ {
        c := [2]int{red, blue}
        for i, j := 1, k; i <= c[j]; i, j = i+1, j^1 {
            c[j] -= i
            ans = max(ans, i)
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function maxHeightOfTriangle(red: number, blue: number): number {
    let ans = 0;
    for (let k = 0; k < 2; ++k) {
        const c: [number, number] = [red, blue];
        for (let i = 1, j = k; i <= c[j]; ++i, j ^= 1) {
            c[j] -= i;
            ans = Math.max(ans, i);
        }
    }
    return ans;
}

Comments