375. Guess Number Higher or Lower II LeetCode Solution
In this guide, you will get 375. Guess Number Higher or Lower II LeetCode Solution with the best time and space complexity. The solution to Guess Number Higher or Lower II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Guess Number Higher or Lower II
We are playing the Guessing Game. The game will work as follows:
I pick a number between 1 and n.
You guess a number.
If you guess the right number, you win the game.
If you guess the wrong number, then I will tell you whether the number I picked is higher or lower, and you will continue guessing.
Every time you guess a wrong number x, you will pay x dollars. If you run out of money, you lose the game.
Given a particular n, return the minimum amount of money you need to guarantee a win regardless of what number I pick.
Example 1:
Input: n = 10
Output: 16
Explanation: The winning strategy is as follows:
– The range is [1,10]. Guess 7.
– If this is my number, your total is $0. Otherwise, you pay $7.
– If my number is higher, the range is [8,10]. Guess 9.
– If this is my number, your total is $7. Otherwise, you pay $9.
– If my number is higher, it must be 10. Guess 10. Your total is $7 + $9 = $16.
– If my number is lower, it must be 8. Guess 8. Your total is $7 + $9 = $16.
– If my number is lower, the range is [1,6]. Guess 3.
– If this is my number, your total is $7. Otherwise, you pay $3.
– If my number is higher, the range is [4,6]. Guess 5.
– If this is my number, your total is $7 + $3 = $10. Otherwise, you pay $5.
– If my number is higher, it must be 6. Guess 6. Your total is $7 + $3 + $5 = $15.
– If my number is lower, it must be 4. Guess 4. Your total is $7 + $3 + $5 = $15.
– If my number is lower, the range is [1,2]. Guess 1.
– If this is my number, your total is $7 + $3 = $10. Otherwise, you pay $1.
– If my number is higher, it must be 2. Guess 2. Your total is $7 + $3 + $1 = $11.
The worst case in all these scenarios is that you pay $16. Hence, you only need $16 to guarantee a win.
Input: n = 1
Output: 0
Explanation: There is only one possible number, so you can guess 1 and not have to pay anything.
Example 3:
Input: n = 2
Output: 1
Explanation: There are two possible numbers, 1 and 2.
– Guess 1.
– If this is my number, your total is $0. Otherwise, you pay $1.
– If my number is higher, it must be 2. Guess 2. Your total is $1.
The worst case is that you pay $1.
Constraints:
1 <= n <= 200
Complexity Analysis
Time Complexity: O(n^3)
Space Complexity: O(n^2)
375. Guess Number Higher or Lower II LeetCode Solution in C++
class Solution {
public:
int getMoneyAmount(int n) {
vector<vector<int>> mem(n + 1, vector<int>(n + 1, INT_MAX));
return getMoneyAmount(1, n, mem);
}
private:
// Returns the minimum money you need to guarantee a win of picking i..j.
int getMoneyAmount(int i, int j, vector<vector<int>>& mem) {
if (i >= j)
return 0;
if (mem[i][j] != INT_MAX)
return mem[i][j];
for (int k = i; k <= j; ++k)
mem[i][j] = min(mem[i][j], max(getMoneyAmount(i, k - 1, mem),
getMoneyAmount(k + 1, j, mem)) +
k);
return mem[i][j];
}
};
/* code provided by PROGIEZ */
375. Guess Number Higher or Lower II LeetCode Solution in Java
class Solution {
public int getMoneyAmount(int n) {
int[][] mem = new int[n + 1][n + 1];
Arrays.stream(mem).forEach(A -> Arrays.fill(A, Integer.MAX_VALUE));
return getMoneyAmount(1, n, mem);
}
// Returns the minimum money you need to guarantee a win of picking i..j.
private int getMoneyAmount(int i, int j, int[][] mem) {
if (i >= j)
return 0;
if (mem[i][j] != Integer.MAX_VALUE)
return mem[i][j];
for (int k = i; k <= j; ++k)
mem[i][j] = Math.min(mem[i][j], Math.max(getMoneyAmount(i, k - 1, mem), //
getMoneyAmount(k + 1, j, mem)) +
k);
return mem[i][j];
}
}
// code provided by PROGIEZ
375. Guess Number Higher or Lower II LeetCode Solution in Python
class Solution:
def getMoneyAmount(self, n: int) -> int:
@functools.lru_cache(None)
def dp(i: int, j: int) -> int:
"""Returns the minimum money you need to guarantee a win of picking i..j.
"""
if i >= j:
return 0
return min(max(dp(i, k - 1), dp(k + 1, j)) + k
for k in range(i, j + 1))
return dp(1, n)
# code by PROGIEZ
