# Posts published in “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] <= bookings[i] <= n <= 20000
• 1 <= bookings[i] <= 10000

## Solution: Marking start and end

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

## 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 two binary strings, return their sum (also a binary string).

The input strings are both non-empty and contains only characters 1 or 0.

Example 1:

Input: a = "11", b = "1"
Output: "100"

Example 2:

Input: a = "1010", b = "1011"
Output: "10101"

Solution: Big integer

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

## C++

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.


Example 2:

Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

Solution: Big Integer

Process from right to left (lest significant to most signification). Use carry to indicate whether need +1 for next digit or not.

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

## c++

In a forest, each rabbit has some color. Some subset of rabbits (possibly all of them) tell you how many other rabbits have the same color as them. Those answers are placed in an array.

Return the minimum number of rabbits that could be in the forest.

Examples:
Input: answers = [1, 1, 2]
Output: 5
Explanation:
The two rabbits that answered "1" could both be the same color, say red.
The rabbit than answered "2" can't be red or the answers would be inconsistent.
Say the rabbit that answered "2" was blue.
Then there should be 2 other blue rabbits in the forest that didn't answer into the array.
The smallest possible number of rabbits in the forest is therefore 5: 3 that answered plus 2 that didn't.

Input: answers = [10, 10, 10]
Output: 11

Output: 0


Note:

1. answers will have length at most 1000.
2. Each answers[i] will be an integer in the range [0, 999].

## Solution: Math

Say there n rabbits answered x.
if n <= x: they can have the same color
if n > x: they must be divided into groups, each group has x + 1 rabbits, and there are at least ceil(n / (x+1)) groups.
So there will be ceil(n / (x + 1)) * (x + 1) rabbits. This expression can be expressed as (n + x) / (x + 1) * (x + 1) in programming languages. (n + x) // (x + 1) * (x + 1) for Python3.

## Python3

Mission News Theme by Compete Themes.