# Posts published in “Math”

Given a date, return the corresponding day of the week for that date.

The input is given as three integers representing the daymonth and year respectively.

Return the answer as one of the following values {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}.

Example 1:

Input: day = 31, month = 8, year = 2019
Output: "Saturday"


Example 2:

Input: day = 18, month = 7, year = 1999
Output: "Sunday"


Example 3:

Input: day = 15, month = 8, year = 1993
Output: "Sunday"


Constraints:

• The given dates are valid dates between the years 1971 and 2100.

Solution: LeapYear

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

## C++

Return the number of permutations of 1 to n so that prime numbers are at prime indices (1-indexed.)

(Recall that an integer is prime if and only if it is greater than 1, and cannot be written as a product of two positive integers both smaller than it.)

Since the answer may be large, return the answer modulo 10^9 + 7.

Example 1:

Input: n = 5
Output: 12
Explanation: For example [1,2,5,4,3] is a valid permutation, but [5,2,3,4,1] is not because the prime number 5 is at index 1.


Example 2:

Input: n = 100
Output: 682289015


Constraints:

• 1 <= n <= 100

## Solution: Permutation

Count the number of primes in range [1, n], assuming there are p primes and n – p non-primes, we can permute each group separately.
ans = p! * (n – p)!

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

## C++

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++

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++

Mission News Theme by Compete Themes.