# Posts tagged as “math”

There are n flights, and they are labeled from 1 to n.

We have a list of flight bookings.  The i-th booking bookings[i] = [i, j, k] means that we booked kseats from flights labeled i to j inclusive.

Return an array answer of length n, representing the number of seats booked on each flight in order of their label.

Example 1:

Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
Output: [10,55,45,25,25]


Constraints:

• 1 <= bookings.length <= 20000
• 1 <= bookings[i][0] <= bookings[i][1] <= n <= 20000
• 1 <= bookings[i][2] <= 10000

## Solution: Marking start and end

Time complexity: O(|bookings|)
Space complexity: O(n)

## C++

In an infinite binary tree where every node has two children, the nodes are labelled in row order.

In the odd numbered rows (ie., the first, third, fifth,…), the labelling is left to right, while in the even numbered rows (second, fourth, sixth,…), the labelling is right to left.

Given the label of a node in this tree, return the labels in the path from the root of the tree to the node with that label.

Example 1:

Input: label = 14
Output: [1,3,4,14]


Example 2:

Input: label = 26
Output: [1,2,6,10,26]


Constraints:

• 1 <= label <= 10^6

## Solution: Math

Time complexity: O(logn)
Space complexity: O(logn)

## C++

Solve a given equation and return the value of x in the form of string “x=#value”. The equation contains only ‘+’, ‘-‘ operation, the variable x and its coefficient.

If there is no solution for the equation, return “No solution”.

If there are infinite solutions for the equation, return “Infinite solutions”.

If there is exactly one solution for the equation, we ensure that the value of x is an integer.

Example 1:

Input: "x+5-3+x=6+x-2"
Output: "x=2"


Example 2:

Input: "x=x"
Output: "Infinite solutions"


Example 3:

Input: "2x=x"
Output: "x=0"


Example 4:

Input: "2x+3x-6x=x+2"
Output: "x=-1"


Example 5:

Input: "x=x+2"
Output: "No solution"

## Solution: Parse the equation

Time complexity: O(n)
Space complexity: O(1)

## C++

Implement pow(xn), which calculates x raised to the power n (xn).

Example 1:

Input: 2.00000, 10
Output: 1024.00000


Example 2:

Input: 2.10000, 3
Output: 9.26100


Example 3:

Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25


Note:

• -100.0 < x < 100.0
• n is a 32-bit signed integer, within the range [−231, 231 − 1]

## Solution: Recursion

square x and cut n in half.
if n is negative, compute 1.0 / pow(x, |n|)

pow(x, n) := pow(x * x, n / 2) * (x if n % 2 else 1)pow(x, 0) := 1
Example:pow(x, 5) = pow(x^2, 2) * x           = pow(x^4, 1) * x           = pow(x^8, 0) * x^4 * x          = 1 * x^4 * x = x^5

Time complexity: O(logn)
Space complexity: O(logn)

## C++

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

## Solution 1: DP

dp[i] := ans
dp[0] = 0
dp[i] = min{dp[i – j * j] + 1} 1 <= j * j <= i

dp[5] = min{
dp[5 – 2 * 2] + 1 = dp[1] + 1 = (dp[1 – 1 * 1] + 1) + 1 = dp[0] + 1 + 1 = 2,
dp[5 – 1 * 1] + 1 = dp[3] + 1 = (dp[3 – 1 * 1] + 1) + 1 = dp[1] + 2 = dp[1 – 1*1] + 1 + 2 = dp[0] + 3 = 3
};

dp[5] = 2

Time complexity: O(n * sqrt(n))
Space complexity: O(n)

## C++

Mission News Theme by Compete Themes.