Posts published in “Math”

花花酱 LeetCode 470. Implement Rand10() Using Rand7()

By zxi on October 15, 2018

Problem

Given a function rand7 which generates a uniform random integer in the range 1 to 7, write a function rand10 which generates a uniform random integer in the range 1 to 10.

Do NOT use system’s Math.random().

Example 1:

Input: 1
Output: [7]

Example 2:

Input: 2
Output: [8,4]

Example 3:

Input: 3
Output: [8,1,10]

Note:

rand7 is predefined.
Each testcase has one argument: n, the number of times that rand10 is called.

Follow up:

What is the expected value for the number of calls to rand7() function?
Could you minimize the number of calls to rand7()?

Solution:

Time complexity: O(1)

Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int rand10() {

int index = INT_MAX;

while (index >= 40)

index = 7 * (rand7() - 1) + (rand7() - 1);

return index % 10 + 1;

}

};

花花酱 LeetCode 923. 3Sum With Multiplicity

By zxi on October 13, 2018

Problem

Given an integer array A, and an integer target, return the number of tuples i, j, k such that i < j < k and A[i] + A[j] + A[k] == target.

As the answer can be very large, return it modulo 10^9 + 7.

Example 1:

Input: A = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20
Explanation: 
Enumerating by the values (A[i], A[j], A[k]):
(1, 2, 5) occurs 8 times;
(1, 3, 4) occurs 8 times;
(2, 2, 4) occurs 2 times;
(2, 3, 3) occurs 2 times.

Example 2:

Input: A = [1,1,2,2,2,2], target = 5
Output: 12
Explanation: 
A[i] = 1, A[j] = A[k] = 2 occurs 12 times:
We choose one 1 from [1,1] in 2 ways,
and two 2s from [2,2,2,2] in 6 ways.

Note:

3 <= A.length <= 3000
0 <= A[i] <= 100
0 <= target <= 300

Solution: Math / Combination

Time complexity: O(n + |target|^2)

Space complexity: O(|target|)

C++

// Author: Huahua, runtime: 4 ms

class Solution {

public:

int threeSumMulti(vector<int>& A, int target) {

constexpr int kMaxN = 100;

constexpr int kMod = 1e9 + 7;

vector<long> c(kMaxN + 1, 0);

for (int a : A) ++c[a];

long ans = 0;

for (int i = 0; i <= target; ++i) {

for (int j = i; j <= target; ++j) {

const int k = target - i - j;

if (k < 0 || k >= c.size() || k < j) continue;

if (!c[i] || !c[j] || !c[k]) continue;

if (i == j && j == k)

ans += (c[i] - 2) * (c[i] - 1) * c[i] / 6;

else if (i == j && j != k)

ans += c[i] * (c[i] - 1) / 2 * c[k];

else if (i != j && j == k)

ans += c[i] * (c[j] - 1) * c[j] / 2;

else

ans += c[i] * c[j] * c[k];

}

return ans % kMod;

}

};

花花酱 LeetCode 914. X of a Kind in a Deck of Cards

By zxi on September 30, 2018

Problem

n a deck of cards, each card has an integer written on it.

Return true if and only if you can choose X >= 2 such that it is possible to split the entire deck into 1 or more groups of cards, where:

Each group has exactly X cards.
All the cards in each group have the same integer.

Example 1:

Input: [1,2,3,4,4,3,2,1]
Output: true
Explanation: Possible partition [1,1],[2,2],[3,3],[4,4]

Example 2:

Input: [1,1,1,2,2,2,3,3]
Output: false
Explanation: No possible partition.

Example 3:

Input: [1]
Output: false
Explanation: No possible partition.

Example 4:

Input: [1,1]
Output: true
Explanation: Possible partition [1,1]

Example 5:

Input: [1,1,2,2,2,2]
Output: true
Explanation: Possible partition [1,1],[2,2],[2,2]

Note:

1 <= deck.length <= 10000
0 <= deck[i] < 10000

Solution 1: HashTable + Brute Force

Try all possible Xs. 2 ~ deck.size()

Time complexity: ~O(n)

Space complexity: O(1)

C++

// Author: Huahua, 16 ms

class Solution {

public:

bool hasGroupsSizeX(vector<int>& deck) {

unordered_map<int, int> counts;

for (int card : deck) ++counts[card];

for (int i = 2; i <= deck.size(); ++i) {

if (deck.size() % i) continue;

bool ok = true;

for (const auto& pair : counts)

if (pair.second % i) {

ok = false;

break;

}

if (ok) return true;

}

return false;

}

};

Solution 2: HashTable + GCD

Time complexity: O(nlogn)

Space complexity: O(1)

C++

// Author: Huahua, 16 ms

class Solution {

public:

bool hasGroupsSizeX(vector<int>& deck) {

unordered_map<int, int> counts;

for (int card : deck) ++counts[card];

int X = deck.size();

for (const auto& p : counts)

X = __gcd(X, p.second);

return X >= 2;

}

};

Java

// Author: Somebody

class Solution {

public boolean hasGroupsSizeX(int[] deck) {

HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

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

int curr = deck[i];

if (map.containsKey(curr)) {

map.put(curr, map.get(curr) + 1);

} else {

map.put(curr, 1);

}

// O(nLogn)

int gcd = 0;

for(Integer key: map.keySet()) {

gcd = findGCDOfTwoNumbers(map.get(key), gcd);

}

return gcd >= 2;

}

// O(Log n)

public static int findGCDOfTwoNumbers (int a, int b) {

if (b == 0) {

return a;

}

return findGCDOfTwoNumbers(b, a%b);

}

花花酱 LeetCode 908. Smallest Range I

By zxi on September 23, 2018

Problem

Given an array A of integers, for each integer A[i] we may choose any x with -K <= x <= K, and add xto A[i].

After this process, we have some array B.

Return the smallest possible difference between the maximum value of B and the minimum value of B.

Example 1:

Input: A = [1], K = 0
Output: 0
Explanation: B = [1]

Example 2:

Input: A = [0,10], K = 2
Output: 6
Explanation: B = [2,8]

Example 3:

Input: A = [1,3,6], K = 3
Output: 0
Explanation: B = [3,3,3] or B = [4,4,4]

Note:

1 <= A.length <= 10000
0 <= A[i] <= 10000
0 <= K <= 10000

Solution 0: Brute Force (TLE)

Try all pairs

Time complexity: O(n^2)

Space complexity: O(1)

Solution 1: Math

Time complexity: O(n)

Space complexity: O(1)

Find the min/max element of the array.

min + k v.s. max – k

ans = max(0, (max – min) – 2 * k))

C++

// Author: Huahua

class Solution {

public:

int smallestRangeI(vector<int>& A, int K) {

int a_min = *min_element(begin(A), end(A));

int a_max = *max_element(begin(A), end(A));

return max(0, (a_max - a_min) - 2 * K);

}

};

Python3

# Author: Huahua, 72 ms

class Solution:

def smallestRangeI(self, A, K):

return max(0, max(A) - min(A) - 2 * K);

花花酱 LeetCode 902. Numbers At Most N Given Digit Set

By zxi on September 13, 2018

Problem

We have a sorted set of digits D, a non-empty subset of {'1','2','3','4','5','6','7','8','9'}. (Note that '0' is not included.)

Now, we write numbers using these digits, using each digit as many times as we want. For example, if D = {'1','3','5'}, we may write numbers such as '13', '551', '1351315'.

Return the number of positive integers that can be written (using the digits of D) that are less than or equal to N.

Example 1:

Input: D = ["1","3","5","7"], N = 100
Output: 20
Explanation: 
The 20 numbers that can be written are:
1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.

Example 2:

Input: D = ["1","4","9"], N = 1000000000
Output: 29523
Explanation: 
We can write 3 one digit numbers, 9 two digit numbers, 27 three digit numbers,
81 four digit numbers, 243 five digit numbers, 729 six digit numbers,
2187 seven digit numbers, 6561 eight digit numbers, and 19683 nine digit numbers.
In total, this is 29523 integers that can be written using the digits of D.

Note:

D is a subset of digits '1'-'9' in sorted order.
1 <= N <= 10^9

Solution -1: DFS (TLE)

Time complexity: O(|D|^log10(N))

Space complexity: O(n)

// Author: Huahua

class Solution {

public:

int atMostNGivenDigitSet(vector<string>& D, int N) {

int ans = 0;

dfs(D, 0, N, ans);

return ans;

}

private:

void dfs(const vector<string>& D, int cur, int N, int& ans) {

if (cur > N) return;

if (cur > 0 && cur <= N) ++ans;

for (const string& d : D)

dfs(D, cur * 10 + d[0] - '0', N, ans);

}

};

Solution 1: Math

Time complexity: O(log10(N))

Space complexity: O(1)

Suppose N has n digits.

less than n digits

We can use all the numbers from D to construct numbers of with length 1,2,…,n-1 which are guaranteed to be less than N.

e.g. n = 52125, D = [1, 2, 5]

format X: e.g. 1, 2, 5 counts = |D| ^ 1

format XX: e.g. 11,12,15,21,22,25,51,52,55, counts = |D|^2

format XXX: counts = |D|^3

format XXXX: counts = |D|^4

exact n digits

if all numbers in D != N[0], counts = |d < N[0] | d in D| * |D|^(n-1), and we are done.

e.g. N = 34567, D = [1,2,8]

we can make:

X |3|^1
XX |3| ^ 2
XXX |3| ^ 3
XXXX |3| ^ 3
1XXXX, |3|^4
2XXXX, |3|^4
we can’t do 8XXXX

Total = (3^1 + 3^2 + 3^3 + 3^4) + 2 * |3|^ 4 = 120 + 162 = 282

N = 52525, D = [1,2,5]

However, if d = N[i], we need to check the next digit…

X |3|^1
XX |3| ^ 2
XXX |3| ^ 3
XXXX |3| ^ 3
1XXXX, |3|^4
2XXXX, |3|^4
5????
- 51XXX |3|^3
- 52???
  - 521XX |3|^2
  - 522XX |3|^2
  - 525??
    - 5251X |3|^1
    - 5252?
      - 52521 |3|^0
      - 52522 |3|^0
      - 52525 +1

total = (120) + 2 * |3|^4 + |3|^3 + 2*|3|^2 + |3|^1 + 2 * |3|^0 + 1 = 120 + 213 = 333

if every digit of N is from D, then we also have a valid solution, thus need to + 1.

C++

class Solution {

public:

int atMostNGivenDigitSet(vector<string>& D, int N) {

const string s = to_string(N);

const int n = s.length();

int ans = 0;

for (int i = 1; i < n; ++i)

ans += pow(D.size(), i);

for (int i = 0; i < n; ++i) {

bool prefix = false;

for (const string& d : D) {

if (d[0] < s[i]) {

ans += pow(D.size(), n - i - 1);

} else if (d[0] == s[i]) {

prefix = true;

break;

}

if (!prefix) return ans;

}

// plus one for solution N itself, all the digits are from D.

return ans + 1;

}

};

Java

// Author: Huahua, 4 ms

class Solution {

public int atMostNGivenDigitSet(String[] D, int N) {

char[] s = String.valueOf(N).toCharArray();

int n = s.length;

int ans = 0;

for (int i = 1; i < n; ++i)

ans += (int)Math.pow(D.length, i);

for (int i = 0; i < n; ++i) {

boolean prefix = false;

for (String d : D) {

if (d.charAt(0) < s[i]) {

ans += Math.pow(D.length, n - i - 1);

} else if (d.charAt(0) == s[i]) {

prefix = true;

break;

}

if (!prefix) return ans;

}

return ans + 1;

}

Python3

# Author: Huahua, 36 ms

class Solution:

def atMostNGivenDigitSet(self, D, N):

s = str(N)

n = len(s)

ans = sum(len(D) ** i for i in range(1, n))

for i, c in enumerate(s):

ans += len(D) ** (n - i - 1) * sum(d < c for d in D)

if c not in D: return ans

return ans + 1