Frontend School

Smallest Number with Squared Value at Least N

DSA
easy

Smallest Number with Squared Value at Least N

Easy
Binary Search
Mathematics

Overview

In Meesho's e-commerce platform, optimizing resource allocation often involves finding thresholds or minimum values that satisfy certain conditions. For instance, determining the minimum number of units x required such that x squared (representing a growth factor or a resource dependency) meets or exceeds a target N. This problem simulates such a scenario, requiring an efficient algorithm to find this minimum x.

What you need to do / Task

Your task is to implement a function findSmallestSquaredRootCandidate that takes a non-negative integer N as input. The function should return the smallest non-negative integer x such that x * x is greater than or equal to N.

You are not allowed to use built-in square root functions (e.g., Math.sqrt() in JavaScript/TypeScript).

Input & output

  • Input:
    • n: A non-negative integer.
  • Output:
    • The smallest non-negative integer x such that x * x >= n.

Clarifications

  • What if N is 0? If N is 0, what should x be? Consider the condition x * x >= 0.
  • What about x * x overflowing? In JavaScript/TypeScript, the number type can represent integers up to 2^53 - 1 precisely. For the given constraints on N, the maximum possible x would be approximately 45000 (since 45000^2 is 2.025 * 10^9). Therefore, x * x will fit within standard number precision without issues.

Examples

1

Example 1

Input:

n = 0

Output:

0

Note:

For N = 0, the smallest non-negative x such that xx >= 0 is x = 0 (00 = 0).

2

Example 2

Input:

n = 8

Output:

3

Note:

For N = 8, we check:

  • 2*2 = 4 (which is < 8)
  • 3*3 = 9 (which is >= 8) Thus, 3 is the smallest non-negative integer x satisfying the condition.
3

Example 3

Input:

n = 9

Output:

3

Note:

For N = 9, we check:

  • 2*2 = 4 (which is < 9)
  • 3*3 = 9 (which is >= 9) Thus, 3 is the smallest non-negative integer x satisfying the condition.

Constraints

Constraints & assumptions

  • 0 <= n <= 2 * 10^9
  • Your solution should aim for optimal time complexity.
  • You must not use any built-in square root functions.

What interviewers evaluate

  • Correctness: The solution must correctly identify the smallest x for all valid inputs, including edge cases like N=0 or N=1.
  • Algorithm Efficiency: Demonstrates understanding and application of binary search for optimal time complexity.
  • Code Quality: Writes clean, readable, and well-structured code.
  • Problem Comprehension: Clearly understands the problem requirements and constraints.

Loading editor...