Start learning free

LESSON 179 OF 409 · LOOPS - CHALLENGES

Find Largest Number in C++ (Time Complexity: O(n))

Practice Read the full explanation

Given a positive number S, find the largest number n such that the sum
12 + 22 + 32 + ... + n2 is less than or equal to S.

For your information, n2 = n * n

Example:

Input: S = 35

Output: 4

Explanation:
12 + 22 + 32 + 42 = 1 + 4 + 9 + 16 = 30
and 30 <= 35
if we add 52 we end up with 55, which exceeds 35
therefore 4 is the answer
Hints:

If we look at the explanation, a simple algorithm comes to mind:
Keep track of the totalSoFar and start iterating from 1 as long as adding number * number to totalSoFar is less than or equal to S.
You continue to add number * number to totalSoFar as long as you don't exceed S
STEP 1 OF 6
    Ctrl + Enter to check

    C++ · LOOPS - CHALLENGES

    Find Largest Number in C++, explained

    Understanding the Problem

    The core challenge of this problem is to find the largest integer n such that the sum of squares from 1 to n does not exceed a given number S. This problem is significant in various mathematical and computational applications, such as optimization problems and resource allocation.

    Potential pitfalls include misunderstanding the sum of squares and not correctly iterating through the numbers to find the largest n.

    Approach

    To solve this problem, we can start with a simple iterative approach:

    1. Initialize a variable to keep track of the total sum of squares.
    2. Iterate through numbers starting from 1, adding the square of each number to the total sum.
    3. Stop when adding the next square would exceed S.

    This naive approach is straightforward but can be optimized further. However, for this problem, the naive approach is efficient enough given the constraints.

    Algorithm

    Here is a step-by-step breakdown of the algorithm:

    1. Initialize totalSum to 0 and n to 0.
    2. Iterate while totalSum + (n+1)*(n+1) <= S:
      • Increment n.
      • Add (n*n) to totalSum.
    3. Return n as the result.

    Code Implementation

    #include <iostream>
using namespace std;

int findLargestN(int S) {
    int totalSum = 0;
    int n = 0;
    
    // Iterate to find the largest n
    while (totalSum + (n + 1) * (n + 1) <= S) {
        n++;
        totalSum += n * n;
    }
    
    return n;
}

int main() {
    int S = 35;
    cout << "The largest n for S = " << S << " is " << findLargestN(S) << endl;
    return 0;
}

    Complexity Analysis

    The time complexity of this approach is O(n), where n is the largest number such that the sum of squares is less than or equal to S. The space complexity is O(1) as we are using a constant amount of extra space.

    Edge Cases

    Potential edge cases include:

    • S being very small (e.g., 1 or 2).
    • S being a perfect square.
    • S being a very large number.

    For example, if S = 1, the output should be 1 because 12 = 1. If S = 2, the output should still be 1 because 12 = 1 and 22 = 4 exceeds 2.

    Testing

    To test the solution comprehensively, consider the following test cases:

    • Simple cases: S = 1, 2, 3, 4, 5
    • Edge cases: S = 0, 1, 2
    • Large cases: S = 1000, 10000, 100000

    Using a testing framework like Google Test can help automate and manage these test cases effectively.

    Thinking and Problem-Solving Tips

    When approaching such problems, consider the following tips:

    • Break down the problem into smaller, manageable parts.
    • Start with a simple, naive solution and then look for optimizations.
    • Think about edge cases and how your solution handles them.
    • Practice similar problems to improve your problem-solving skills.

    Conclusion

    In this blog post, we discussed how to find the largest number n such that the sum of squares from 1 to n is less than or equal to a given number S. We explored a simple iterative approach, provided a detailed algorithm, and analyzed its complexity. Understanding and solving such problems is crucial for developing strong problem-solving skills in programming.

    Additional Resources

    For further reading and practice, consider the following resources:

    Keep going with C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free