3959. Check Good Integer
Problem Description
You are given a positive integer n.
Let digitSum be the sum of the digits of n, and let squareSum be the sum of the squares of the digits of n.
An integer is called good if squareSum - digitSum >= 50.
Your task is to determine whether n is good. Return true if n is good; otherwise, return false.
In other words, for each digit x in n, you compute its contribution to squareSum as x * x and its contribution to digitSum as x. The difference for each digit is therefore x * x - x, which equals x * (x - 1). Summing this difference over all digits of n gives the value of squareSum - digitSum. If this total is greater than or equal to 50, the integer is good.
How We Pick the Algorithm
Why Simulation / Basic DSA?
This problem maps to Simulation / Basic DSA through a short path in the full flowchart.
Following the described procedure step by step produces the solution.
Open in FlowchartIntuition
The problem asks us to compare squareSum - digitSum against 50. A direct approach would be to compute squareSum and digitSum separately, then subtract one from the other. However, we can simplify this.
Notice that squareSum - digitSum can be rewritten by combining the contributions of each digit. For a single digit x, its contribution to squareSum is x * x and its contribution to digitSum is x. Therefore, its net contribution to the difference is x * x - x, which factors neatly into x * (x - 1).
This means we only need to traverse the digits of n once. For each digit x, we add x * (x - 1) to a running total s. To extract the digits, we repeatedly use divmod(n, 10), which gives us both the remaining number and the last digit in one step.
After processing every digit, the value of s exactly equals squareSum - digitSum. We then simply check whether s >= 50 and return the boolean result accordingly. This single-pass accumulation avoids maintaining two separate sums and directly yields the answer.
Solution Approach
Solution 1: Simulation
We use a variable s to record the result of the square sum minus the digit sum of n. If s is greater than or equal to 50, we return true; otherwise, we return false.
The implementation works as follows:
-
Initialize a variable
sto0. This will accumulate the value ofsquareSum - digitSum. -
Loop while
nis nonzero. In each iteration, usedivmod(n, 10)to simultaneously obtain the new value ofn(the number with its last digit removed) andx(the last digit). This is a clean way to peel off digits one at a time from the right. -
For each extracted digit
x, addx * (x - 1)tos. As explained earlier,x * (x - 1)equalsx * x - x, which is the net contribution of that digit tosquareSum - digitSum. -
Once the loop finishes (when
nbecomes0), the variablesholds the exact value ofsquareSum - digitSumacross all digits. -
Return the result of the comparison
s >= 50.
The time complexity is O(log n), where log n corresponds to the number of digits in n, since we process each digit exactly once. The space complexity is O(1), as we only use a constant amount of extra space for the accumulator and the loop variables.
Example Walkthrough
Let's trace through the solution with a small example: n = 137.
We want to determine if 137 is good, meaning we need to check whether squareSum - digitSum >= 50.
Setup: Initialize s = 0. This accumulator will hold the running value of squareSum - digitSum.
Iteration 1: n = 137
- Apply
divmod(137, 10)→ quotient13, remainder7. Sonbecomes13and the digitx = 7. - Compute the digit's contribution:
x * (x - 1) = 7 * 6 = 42. - Update:
s = 0 + 42 = 42.
Iteration 2: n = 13
- Apply
divmod(13, 10)→ quotient1, remainder3. Sonbecomes1and the digitx = 3. - Compute the digit's contribution:
x * (x - 1) = 3 * 2 = 6. - Update:
s = 42 + 6 = 48.
Iteration 3: n = 1
- Apply
divmod(1, 10)→ quotient0, remainder1. Sonbecomes0and the digitx = 1. - Compute the digit's contribution:
x * (x - 1) = 1 * 0 = 0. - Update:
s = 48 + 0 = 48.
Loop ends because n is now 0.
Verification: Let's confirm with the direct definition:
digitSum = 7 + 3 + 1 = 11squareSum = 49 + 9 + 1 = 59squareSum - digitSum = 59 - 11 = 48✓
This matches our accumulated s = 48.
Final check: Return s >= 50, which is 48 >= 50 → false.
So 137 is not good. This example illustrates how accumulating x * (x - 1) for each digit in a single pass directly yields squareSum - digitSum, avoiding the need to track two separate sums.
Solution Implementation
1class Solution:
2 def checkGoodInteger(self, n: int) -> bool:
3 # Accumulate the weighted value of each digit
4 total = 0
5 while n:
6 # Strip the last digit: 'n' becomes the remaining number, 'digit' is the last digit
7 n, digit = divmod(n, 10)
8 # Add the digit's contribution: digit * (digit - 1)
9 total += digit * (digit - 1)
10 # The integer is considered "good" if the accumulated total reaches the threshold
11 return total >= 50
121class Solution {
2 /**
3 * Checks whether the sum of x * (x - 1) for every digit x of n is at least 50.
4 *
5 * @param n the input integer whose digits will be evaluated
6 * @return true if the accumulated sum reaches 50 or more, false otherwise
7 */
8 public boolean checkGoodInteger(int n) {
9 // Accumulator for the sum of x * (x - 1) over all digits.
10 int sum = 0;
11
12 // Process the number digit by digit, from least significant to most significant.
13 for (; n > 0; n /= 10) {
14 // Extract the current last digit.
15 int digit = n % 10;
16
17 // Add the contribution of this digit to the running sum.
18 sum += digit * (digit - 1);
19 }
20
21 // The integer is "good" only when the total reaches the threshold of 50.
22 return sum >= 50;
23 }
24}
25```
26
27**A note on correctness:** The current implementation only handles positive `n` (the loop condition `n > 0` skips `n == 0` and negative values). If you also need to support `n == 0` or negative numbers, consider taking the absolute value first and adjusting the loop condition. Here's an alternative perspective that covers those cases:
28
29```java
30class Solution {
31 public boolean checkGoodInteger(int n) {
32 // Work with the absolute value so negative inputs are handled consistently.
33 long value = Math.abs((long) n); // long avoids Integer.MIN_VALUE overflow
34
35 int sum = 0;
36
37 // Use a do-while so that n == 0 is still processed once.
38 do {
39 int digit = (int) (value % 10);
40 sum += digit * (digit - 1);
41 value /= 10;
42 } while (value > 0);
43
44 return sum >= 50;
45 }
46}
471class Solution {
2public:
3 bool checkGoodInteger(int n) {
4 // Accumulator for the weighted sum of all digits
5 int sum = 0;
6
7 // Iterate over each digit by repeatedly dividing by 10
8 for (; n > 0; n /= 10) {
9 // Extract the least significant digit
10 int digit = n % 10;
11
12 // Add the contribution of this digit: digit * (digit - 1)
13 sum += digit * (digit - 1);
14 }
15
16 // The integer is "good" if the accumulated sum reaches the threshold
17 return sum >= 50;
18 }
19};
201/**
2 * Determines whether the given integer is "good".
3 * A number is considered good when the sum of the value `digit * (digit - 1)`
4 * over all of its decimal digits is greater than or equal to 50.
5 *
6 * @param n - The non-negative integer to evaluate.
7 * @returns `true` if the computed sum is at least 50, otherwise `false`.
8 */
9function checkGoodInteger(n: number): boolean {
10 // Accumulator for the sum of digit * (digit - 1) across all digits.
11 let sum: number = 0;
12
13 // Process each decimal digit from least significant to most significant.
14 for (; n; n = Math.floor(n / 10)) {
15 // Extract the current least significant digit.
16 const digit: number = n % 10;
17
18 // Add this digit's contribution: digit * (digit - 1).
19 // Note: this yields 0 for digits 0 and 1, and increases for larger digits.
20 sum += digit * (digit - 1);
21 }
22
23 // The integer is "good" when the total reaches the threshold of 50.
24 return sum >= 50;
25}
26Time and Space Complexity
-
Time Complexity:
O(log n). Thewhileloop iterates once per digit ofn, extracting one digit on each iteration viadivmod(n, 10). The number of digits innis⌊log₁₀ n⌋ + 1, so the loop runsO(log n)times. Each iteration performs constant-time arithmetic operations, giving an overall time complexity ofO(log n). -
Space Complexity:
O(1). Only a fixed number of variables (s,n,x) are used regardless of the input size, so the space usage is constant.
Common Pitfalls
Pitfall 1: Misinterpreting the formula and computing squareSum - digitSum incorrectly
A frequent mistake is mixing up the order of operations or the relationship between the square sum and the digit sum. Some attempt to compute the difference per digit as x - x * x (reversed subtraction) or accidentally write x * x - 1 instead of x * x - x. These errors produce a value with the wrong sign or magnitude, leading to incorrect results.
Why it happens: The identity x * x - x = x * (x - 1) is a convenient simplification, but if you forget the factoring step you might mistype it. For instance, writing digit * digit - 1 instead of digit * (digit - 1) changes the contribution of every digit.
Solution: Either stick faithfully to the factored form digit * (digit - 1), or compute both sums separately and subtract them at the end. The separate-sum approach is more verbose but self-documenting:
class Solution:
def checkGoodInteger(self, n: int) -> bool:
digit_sum = 0
square_sum = 0
while n:
n, digit = divmod(n, 10)
digit_sum += digit
square_sum += digit * digit
return square_sum - digit_sum >= 50
This makes the intent unmistakable and avoids the risk of a malformed shortcut expression.
Pitfall 2: Using int(n) conversion or string iteration without handling the input type
Another common issue arises when developers iterate over the digits by converting n to a string (e.g., for ch in str(n)). While this works for positive integers, problems can surface if n is passed as a string already, or if leading/trailing whitespace exists. The divmod approach in the provided solution sidesteps this by working purely with arithmetic.
Why it happens: String-based iteration feels natural, but it introduces dependency on the exact representation of the input and requires careful int(ch) conversion for each character.
Solution: Prefer the arithmetic divmod extraction (as in the original code) for robustness, or if using strings, ensure proper conversion:
class Solution:
def checkGoodInteger(self, n: int) -> bool:
return sum(int(ch) * (int(ch) - 1) for ch in str(n)) >= 50
Pitfall 3: Off-by-one in the threshold comparison
The condition specifies "greater than or equal to 50" (>= 50). A subtle bug is using a strict inequality > 50, which would incorrectly reject a value of exactly 50.
Why it happens: It's easy to skim past the "or equal to" portion of the requirement and assume a strict comparison.
Solution: Carefully match the problem statement and use >= 50. When the boundary value matters, add a test case where the total equals exactly 50 to confirm the comparison behaves correctly.
Ready to land your dream job?
Unlock your dream job with a 5-minute quiz for a personalized study roadmap!
Get My RoadmapWhat data structure does Breadth-first search typically uses to store intermediate states?
Recommended Readings
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion If you prefer videos here's a video that explains recursion in a fun and easy way Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask him
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity describes how the time needed
Want a Structured Path to Master System Design Too? Don’t Miss This!