# Posts tagged as “math”

Problem:

Implement int sqrt(int x).

Compute and return the square root of x.

x is guaranteed to be a non-negative integer.

Example 1:

Example 2:

# Solution 1: Brute force

Time complexity: sqrt(x)

# Solution 2: Binary search

Time complexity: O(logn)

# Solution 3: Newton’s method

## Python3

Problem:

You are standing at position 0 on an infinite number line. There is a goal at position target.

On each move, you can either go left or right. During the n-th move (starting from 1), you take n steps.

Return the minimum number of steps required to reach the destination.

Example 1:

Example 2:

Note:

• target will be a non-zero integer in the range [-10^9, 10^9].

Idea:

Math

Time complexity: O(sqrt(target))

Space complexity: O(1)

O(1)

Problem:

Count the number of prime numbers less than a non-negative number, n.

Idea:

Sieve of Eratosthenes

Time Complexity:

O(nloglogn)

Space Complexity:

O(n)

Solution:

C++

Java

Python3

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +- and *.

Example 1:

Input: "2-1-1".

Output: [0, 2]

Example 2:

Input: "2*3-4*5"

Output: [-34, -14, -10, -10, 10]

Solution:

Running time: 3ms