Posts published in “Math”

花花酱 LeetCode 878. Nth Magical Number

By zxi on July 28, 2018

Problem

A positive integer is magical if it is divisible by either A or B.

Return the N-th magical number. Since the answer may be very large, return it modulo 10^9 + 7.

Example 1:

Input: N = 1, A = 2, B = 3
Output: 2

Example 2:

Input: N = 4, A = 2, B = 3
Output: 6

Example 3:

Input: N = 5, A = 2, B = 4
Output: 10

Example 4:

Input: N = 3, A = 6, B = 4
Output: 8

Note:

1 <= N <= 10^9
2 <= A <= 40000
2 <= B <= 40000

Solution: Math + Binary Search

Let n denote the number of numbers <= X that are divisible by either A or B.

n = X / A + X / B – X / lcm(A, B) = X / A + X / B – X / (A * B / gcd(A, B))

Binary search for the smallest X such that n >= N

Time complexity: O(log(1e9*4e5)

Space complexity: O(1)

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

int nthMagicalNumber(int N, int A, int B) {

const int kMod = 1000000007;

long l = 2;

long r = static_cast<long>(1e9 * 4e5);

int d = gcd(A, B);

while (l < r) {

long m = (r - l) / 2 + l;

if (m / A + m / B - m / (A * B / d) < N)

l = m + 1;

else

r = m;

}

return l % kMod;

}

private:

int gcd(int a, int b) {

if (a % b == 0) return b;

return gcd(b, a % b);

}

};

花花酱 LeetCode 880. Random Pick with Weight

By zxi on July 28, 2018

Problem

Given an array w of positive integers, where w[i] describes the weight of index i, write a function pickIndex which randomly picks an index in proportion to its weight.

Note:

1 <= w.length <= 10000
1 <= w[i] <= 10^5
pickIndex will be called at most 10000 times.

Example 1:

Input: 
["Solution","pickIndex"]
[[[1]],[]]
Output: [null,0]

Example 2:

Input: 
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output: [null,0,1,1,1,0]

Explanation of Input Syntax:

The input is two lists: the subroutines called and their arguments. Solution‘s constructor has one argument, the array w. pickIndex has no arguments. Arguments are always wrapped with a list, even if there aren’t any.

Solution: Binary Search

Convert PDF to CDF
Uniformly sample a value s in [1, sum(weights)].
Use binary search to find first index such that PDF[index] >= s.

Time complexity: Init O(n), query O(logn)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 184 ms

class Solution {

public:

Solution(vector<int> w) {

sums_ = std::move(w);

for (int i = 1; i < sums_.size(); ++i)

sums_[i] += sums_[i - 1];

}

int pickIndex() {

int s = rand() / static_cast<double>(RAND_MAX) * sums_.back() + 1;

return lower_bound(sums_.begin(), sums_.end(), s) - sums_.begin();

// or

// int l = 0;

// int r = sums_.size();

// while (l < r) {

// int m = (r - l) / 2 + l;

// if (sums_[m] < s)

// l = m + 1;

// else

// r = m;

// }

// return l;

}

private:

vector<int> sums_;

};

Problem

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"

Note:

The length of both num1 and num2 is < 110.
Both num1 and num2 contain only digits 0-9.
Both num1 and num2 do not contain any leading zero, except the number 0 itself.
You must not use any built-in BigInteger library or convert the inputs to integer directly.

Solution: Simulation

Simulate multiplication one digit at a time.

Time complexity: O(l1*l2)

Space complexity: O(l1 + l2)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

string multiply(string num1, string num2) {

const int l1 = num1.length();

const int l2 = num2.length();

string ans(l1 + l2, '0');

for (int i = l1 - 1; i >= 0; --i)

for (int j = l2 - 1; j >= 0; --j) {

int sum = (ans[i + j + 1] - '0') + (num1[i] - '0') * (num2[j] - '0');

ans[i + j + 1] = (sum % 10) + '0';

ans[i + j] += sum / 10;

}

for (int i = 0; i < ans.length(); ++i)

if (ans[i] != '0' || i == ans.length() - 1) return ans.substr(i);

return "";

}

};

花花酱 LeetCode 357. Count Numbers with Unique Digits

By zxi on July 16, 2018

Problem

Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10ⁿ.

Example:
Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99])

Solution: Math

f(0) = 1 (0)

f(1) = 10 (0 – 9)

f(2) = 9 * 9 (1-9 * (0 ~ 9 exclude the one from first digit))

f(3) = 9 * 9 * 8

f(4) = 9 * 9 * 8 * 7

…

f(x) = 0 if x >= 10

ans = sum(f[1] ~ f[n])

Time complexity: O(1)

Space complexity: O(1)

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

int countNumbersWithUniqueDigits(int n) {

if (n == 0) return 1;

vector<int> f(11);

f[1] = 10;

f[2] = 9 * 9;

for (int i = 3; i <= 10; ++i)

f[i] = f[i - 1] * (10 - i + 1);

int ans = 0;

for (int i = 0; i <= min(10, n); ++i)

ans += f[i];

return ans;

}

};

花花酱 LeetCode 867. Prime Palindrome

By zxi on July 8, 2018

Problem

Find the smallest prime palindrome greater than or equal to N.

Recall that a number is prime if it’s only divisors are 1 and itself, and it is greater than 1.

For example, 2,3,5,7,11 and 13 are primes.

Recall that a number is a palindrome if it reads the same from left to right as it does from right to left.

For example, 12321 is a palindrome.

Example 1:

Input: 6
Output: 7

Example 2:

Input: 8
Output: 11

Example 3:

Input: 13
Output: 101

Note:

1 <= N <= 10^8
The answer is guaranteed to exist and be less than 2 * 10^8.

Solution: Math

All odd digits palindromes have a factor 11, they are not prime except 11 itself.

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

int primePalindrome(int N) {

if (N <= 2) return 2;

if (N % 2 == 0) ++N;

while (true) {

if (reverse(N) == N && isPrime(N))

return N;

N += 2;

if (N > 11 & (int)log10(N) % 2 == 1)

// 13 -> 101

// 1001 -> 10001

N = pow(10, (int)log10(N) + 1) + 1;

}

return -1;

}

private:

int reverse(int n) {

int r = 0;

while (n) {

r = 10 * r + n % 10;

n /= 10;

}

return r;

}

bool isPrime(int n) {

if (n <= 1) return false;

for (int i = 2; i <= sqrt(n); ++i)

if (n % i == 0) return false;

return true;

}

};

Posts published in “Math”

花花酱 LeetCode 878. Nth Magical Number

Problem

Solution: Math + Binary Search

花花酱 LeetCode 880. Random Pick with Weight

Problem

Solution: Binary Search

Related Problems

花花酱 LeetCode 43. Multiply Strings

Problem

Solution: Simulation

花花酱 LeetCode 357. Count Numbers with Unique Digits

Problem

Solution: Math

花花酱 LeetCode 867. Prime Palindrome

Problem

Solution: Math