# Posts published in “Math”

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)

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

Example 1:

Example 2:

Idea:

Binary search

Solution:

C++

Time complexity: O(log(num))

Space complexity: O(1)

Problem:

self-dividing number is a number that is divisible by every digit it contains.

For example, 128 is a self-dividing number because 128 % 1 == 0128 % 2 == 0, and 128 % 8 == 0.

Also, a self-dividing number is not allowed to contain the digit zero.

Given a lower and upper number bound, output a list of every possible self dividing number, including the bounds if possible.

Example 1:

Note:

• The boundaries of each input argument are 1 <= left <= right <= 10000.

Idea: Brute Force

Time Complexity: O(n)

Space Complexity: O(1)

Solution:

C++

String

Related Problems:

Problem:

Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.

For example,
Given nums = [0, 1, 3] return 2.

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

Idea:

sum / xor Solution:

# Problem:

Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

Example 1:

Input: [2,2,3,4]
Output: 3
Explanation:
Valid combinations are:
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3


Note:

1. The length of the given array won’t exceed 1000.
2. The integers in the given array are in the range of [0, 1000].

# Idea:

Greedy Time Complexity:

O(n^2)