Start learning free

LESSON 180 OF 410 · LOOPS - CHALLENGES

Find Largest Number in Python (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

    PYTHON · LOOPS - CHALLENGES

    Find Largest Number in Python, 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 use 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 the iteration when adding the next square would exceed S.
    4. The last valid number before exceeding S is the answer.

    Let's discuss a naive solution and then optimize it:

    Naive Solution

    The naive solution involves iterating through each number, calculating its square, and adding it to a running total until the total exceeds S. This approach is straightforward but can be inefficient for large values of S.

    Optimized Solution

    The optimized solution follows the same iterative approach but ensures that we stop as soon as the sum exceeds S. This approach is efficient with a time complexity of O(n), where n is the largest number whose square sum is less than or equal to S.

    Algorithm

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

    1. Initialize total_sum to 0 and n to 0.
    2. Iterate while total_sum + (n+1)^2 is less than or equal to S:
      • Increment n by 1.
      • Add n^2 to total_sum.
    3. Return n as the result.

    Code Implementation

    def find_largest_n(S):
    # Initialize total sum and n
    total_sum = 0
    n = 0
    
    # Iterate while the next square sum is within the limit S
    while total_sum + (n + 1) ** 2 <= S:
        n += 1
        total_sum += n ** 2
    
    return n

# Example usage
S = 35
print(find_largest_n(S))  # Output: 4

    Complexity Analysis

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

    Edge Cases

    Consider the following edge cases:

    • S is very small (e.g., 1). The function should return 1.
    • S is a perfect square sum (e.g., 14). The function should return the correct n.
    • S is very large. The function should handle large inputs efficiently.

    Testing

    To test the solution comprehensively, consider a variety of test cases:

    def test_find_largest_n():
    assert find_largest_n(1) == 1
    assert find_largest_n(5) == 2
    assert find_largest_n(14) == 3
    assert find_largest_n(30) == 4
    assert find_largest_n(35) == 4
    assert find_largest_n(50) == 5
    assert find_largest_n(100) == 6
    print("All test cases pass")

test_find_largest_n()

    Thinking and Problem-Solving Tips

    When approaching such problems, consider the following tips:

    • Break down the problem into smaller, manageable parts.
    • Think about the constraints and edge cases.
    • Start with a simple solution and then optimize it.
    • Practice similar problems to improve 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 implemented the solution in Python. We also analyzed the complexity and discussed edge cases and testing strategies.

    Understanding and solving such problems is crucial for developing strong problem-solving skills. Keep practicing and exploring further to improve your abilities.

    Additional Resources

    For further reading and practice, consider the following resources:

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