Dare2Solve
The problem involves arranging red and blue balls into rows such that each row has an increasing number of balls and adjacent rows alternate colors. The goal is to maximize the height of the triangle formed by these balls.
Recursive Simulation:
Backtracking with Memorization:
Base Cases:
Maximization:
Time Complexity:
Space Complexity:
return Math.max(solve(red, blue), solve(blue, red));
solve(red, blue)
: Computes the maximum height starting with red balls.solve(blue, red)
: Computes the maximum height starting with blue balls.solve
)var solve = function (a, b) {
var flag = true;
for (var i = 1; ; ++i, flag = !flag) {
solve
that takes two parameters, a
and b
, representing the remaining red and blue balls, respectively.for
loop to simulate the construction of each row of the triangle.flag
alternates between true
(red) and false
(blue) to determine which color of balls to place in each row.if (flag) {
if (a < i) return i - 1;
a -= i;
} else {
if (b < i) return i - 1;
b -= i;
}
solve
function's loop:
a >= i
for red, b >= i
for blue) to form the current row.i - 1
, which represents the height of the triangle formed so far.a -= i
for red, b -= i
for blue) from the respective counters.class Solution {
public:
int maxHeightOfTriangle(int red, int blue) {
return max(solve(red, blue), solve(blue, red));
}
private:
int solve(int a, int b) {
bool flag = true;
for (int i = 1; ; ++i, flag = !flag) {
if (flag) {
if (a < i) return i - 1;
a -= i;
} else {
if (b < i) return i - 1;
b -= i;
}
}
}
};
class Solution:
def maxHeightOfTriangle(self, red: int, blue: int) -> int:
return max(self.solve(red, blue), self.solve(blue, red))
def solve(self, a: int, b: int) -> int:
flag = True
i = 1
while True:
if flag:
if a < i:
return i - 1
a -= i
else:
if b < i:
return i - 1
b -= i
i += 1
flag = not flag
class Solution {
public int maxHeightOfTriangle(int red, int blue) {
return Math.max(solve(red, blue), solve(blue, red));
}
private int solve(int a, int b) {
boolean flag = true;
for (int i = 1; ; ++i, flag = !flag) {
if (flag) {
if (a < i) return i - 1;
a -= i;
} else {
if (b < i) return i - 1;
b -= i;
}
}
}
}
/**
* @param {number} red
* @param {number} blue
* @return {number}
*/
var maxHeightOfTriangle = function (red, blue) {
return Math.max(solve(red, blue), solve(blue, red));
};
var solve = function (a, b) {
var flag = true;
for (i = 1; ; ++i, flag = !flag) {
if (flag) {
if (a < i) return i - 1;
a -= i;
} else {
if (b < i) return i - 1;
b -= i;
}
}
};