General
LeetCode 3870 & 3871: from a simple to a general solution
0not0 Dev.to (EN Zone)
22 views
LeetCode problems 3870 and 3871 clearly show the transition from a simple case to a generalized one depending on the constraints. I would say this is a good example of why you should always ask about the problem constraints.
The problems are very similar, but different constraints lead to completely different solutions.
Both problems have the same description:
You are given an integer n.
Return the total number of commas used when writing all integers from [1, n] (inclusive) in standard number formatting.
In standard formatting:
A comma is inserted after every three digits from the right.
Numbers with fewer than 4 digits contain no commas.
And the answer to which solution we should choose lies in the constraints themselves.
For 3870 constrain is 1 <= n <= 105
For 3871 constrain is 1 <= n <= 1015
3870. Count Commas in Range I: the constraints allow us to take advantage of the fact that each number can have at most one comma - a simple solution.
1 ... 999 has 0 commas
1000 ... n has 1 comma
That is why we use max(0, n - 999) in the solution.
class Solution {
public:
int countCommas(int n) {
return max(0, n - 999);
}
};
3871. Count Commas in Range II: n can be much larger (n <= 1015 ), so numbers can contain 2, 3, 4, or 5 commas, which requires a more general solution.
The idea from LeetCode 3870 is no longer enough for LeetCode 3871 because numbers can now contain more than one comma.
>= 1,000 +1 comma
>= 1,000,000 +1 additional comma
>= 1,000,000,000 +1 additional comma
...
Need to understand: for 3871 due to the specific constraint, the loop runs only a few times at most, so within the given constraints, it can also be considered constant-time bounded work.
Since a new comma appears every three additional digits we have start *= 1000.
class Solution {
public:
long long countCommas(long long n) {
long long result = 0;
for(long long start = 1000; start <= n; start *= 1000)
result += n - start + 1;
return result;
}
};
Read original: https://dev.to/0not0/leetcode-3870-3871-from-a-simple-to-a-general-solution-ac9
← Previous
Treat the Model Like Any Other Flaky Network Call
Next →
Your Reputation Is Built From Small Promises
Related
Semantic tag vs Non-Semantic tag
General
51
Dev.to (EN Zone)
How LinkedIn "Bold" Text Actually Works (It's Not Bold At All)
General
43
Dev.to (EN Zone)
Google ADK Callbacks Are a Policy Plane, Not Just Hooks
General
44
DEV Community 周榜
How I Modelled My Power BI Data — Data Modelling, Relationships & Joins (Kenya Crops Dataset)
General
41
DEV Community 周榜
Comments0
No comments yet — be the first