Facebook Pixel

3959. Check Good Integer

Easy
LeetCode ↗

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.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

How We Pick the Algorithm

Why Simulation / Basic DSA?

This problem maps to Simulation / Basic DSA through a short path in the full flowchart.

DirecttransformationoryesComplexdatastructure?noSimulation /Basic DSA

Following the described procedure step by step produces the solution.

Open in Flowchart

Intuition

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:

  1. Initialize a variable s to 0. This will accumulate the value of squareSum - digitSum.

  2. Loop while n is nonzero. In each iteration, use divmod(n, 10) to simultaneously obtain the new value of n (the number with its last digit removed) and x (the last digit). This is a clean way to peel off digits one at a time from the right.

  3. For each extracted digit x, add x * (x - 1) to s. As explained earlier, x * (x - 1) equals x * x - x, which is the net contribution of that digit to squareSum - digitSum.

  4. Once the loop finishes (when n becomes 0), the variable s holds the exact value of squareSum - digitSum across all digits.

  5. 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) → quotient 13, remainder 7. So n becomes 13 and the digit x = 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) → quotient 1, remainder 3. So n becomes 1 and the digit x = 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) → quotient 0, remainder 1. So n becomes 0 and the digit x = 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 = 11
  • squareSum = 49 + 9 + 1 = 59
  • squareSum - digitSum = 59 - 11 = 48

This matches our accumulated s = 48.

Final check: Return s >= 50, which is 48 >= 50false.

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
12
1class 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}
47
1class 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};
20
1/**
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}
26

Time and Space Complexity

  • Time Complexity: O(log n). The while loop iterates once per digit of n, extracting one digit on each iteration via divmod(n, 10). The number of digits in n is ⌊log₁₀ n⌋ + 1, so the loop runs O(log n) times. Each iteration performs constant-time arithmetic operations, giving an overall time complexity of O(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 Roadmap
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

What data structure does Breadth-first search typically uses to store intermediate states?


Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More