mirror of
https://github.com/Manoj-HV30/dsa-competitive-programming.git
synced 2026-05-16 19:35:22 +00:00
18 lines
1.4 KiB
C++
18 lines
1.4 KiB
C++
class Solution{
|
|
public:
|
|
int minPartitions(string n){
|
|
int ans = 0;
|
|
for(char& c : n){
|
|
ans = max(ans, c-'0');
|
|
if(ans==9) break;
|
|
}
|
|
return ans;
|
|
}
|
|
};
|
|
//TC: o(n), SC : o(1)
|
|
|
|
//My first greedy problem.The greedy approach works because each deci-binary number can contribute at most 1 to any digit position, so if a digit in the number is d, we need at least d deci-binary numbers to build that column. This makes the maximum digit in the string the tightest constraint (bottleneck). Since we cannot use fewer than that many numbers and we can always construct exactly that many layers to form the number, the answer is simply the maximum digit. We make one optimal local decision (take the largest digit) and it directly gives the globally optimal solution, which is why this is a greedy approach.
|
|
|
|
|
|
//For c - '0', characters in C++ are stored using ASCII values, where '0' is 48, '1' is 49, up to '9' as 57. When you subtract '0' from a digit character like '7', both characters are implicitly promoted to integers, so the operation becomes 55 - 48 = 7, giving the numeric value of the digit. This works because '0' is a single character. However, "0" is a string literal (a pointer to a character array), not a character, so it cannot be used in arithmetic like this. c-"0"[0] would work tho.
|