Start learning free

LESSON 180 OF 410 · LOOPS - CHALLENGES

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

    JAVASCRIPT · LOOPS - CHALLENGES

    Find Largest Number in JavaScript, 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 possible n.

    Approach

    To solve this problem, we can start with a naive approach and then optimize it:

    Naive Approach

    The naive approach involves iterating through numbers starting from 1 and calculating the sum of their squares until the sum exceeds S. This approach is straightforward but not optimal for large values of S.

    Optimized Approach

    An optimized approach involves using a loop to keep track of the sum of squares and stopping as soon as the sum exceeds S. This approach is more efficient and has a time complexity of O(n).

    Algorithm

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

    1. Initialize totalSoFar to 0 and n to 0.
    2. Iterate through numbers starting from 1.
    3. In each iteration, add the square of the current number to totalSoFar.
    4. If totalSoFar exceeds S, break the loop.
    5. Otherwise, increment n.
    6. Return the value of n.

    Code Implementation

    function findLargestNumber(S) {
  // Initialize totalSoFar to 0 and n to 0
  let totalSoFar = 0;
  let n = 0;

  // Iterate through numbers starting from 1
  for (let i = 1; ; i++) {
    // Add the square of the current number to totalSoFar
    totalSoFar += i * i;

    // If totalSoFar exceeds S, break the loop
    if (totalSoFar > S) {
      break;
    }

    // Increment n
    n++;
  }

  // Return the value of n
  return n;
}

// Example usage:
console.log(findLargestNumber(35)); // Output: 4

    Complexity Analysis

    The time complexity of the optimized 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 is very small (e.g., 1 or 2).
    • S is a perfect square.
    • S is a very large number.

    Each algorithm handles these edge cases by iterating through the numbers and checking the sum of squares.

    Testing

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

    console.log(findLargestNumber(1)); // Output: 1
console.log(findLargestNumber(5)); // Output: 2
console.log(findLargestNumber(14)); // Output: 3
console.log(findLargestNumber(30)); // Output: 4
console.log(findLargestNumber(100)); // Output: 6

    Use testing frameworks like Jest or Mocha for automated testing.

    Thinking and Problem-Solving Tips

    When approaching such problems:

    • Break down the problem into smaller 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

    Understanding and solving such problems is crucial for developing strong problem-solving skills. Practice regularly and explore different approaches to enhance your understanding.

    Additional Resources

    For further reading and practice problems, check out:

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