Posts published in September 2018

花花酱 LeetCode 668. Kth Smallest Number in Multiplication Table

By zxi on September 10, 2018

Problem

Nearly every one have used the Multiplication Table. But could you find out the k-th smallest number quickly from the multiplication table?

Given the height m and the length n of a m * n Multiplication Table, and a positive integer k, you need to return the k-th smallest number in this table.

Example 1:

Input: m = 3, n = 3, k = 5
Output: 
Explanation: 
The Multiplication Table:
1	2	3
2	4	6
3	6	9

The 5-th smallest number is 3 (1, 2, 2, 3, 3).

Example 2:

Input: m = 2, n = 3, k = 6
Output: 
Explanation: 
The Multiplication Table:
1	2	3
2	4	6

The 6-th smallest number is 6 (1, 2, 2, 3, 4, 6).

Note:

The m and n will be in the range [1, 30000].
The k will be in the range [1, m * n]

Solution 1: Nth element (MLE)

Time complexity: O(mn)

Space complexity: O(mn)

C++

// 59 / 69 test cases passed.

class Solution {

public:

int findKthNumber(int m, int n, int k) {

vector<int> s(m * n);

auto it = begin(s);

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

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

*it++ = i * j;

nth_element(begin(s), begin(s) + k - 1, end(s));

return s[k - 1];

}

};

Solution2 : Binary Search

Find first x such that there are k elements less or equal to x in the table.

Time complexity: O(m*log(m*n))

Space complexity: O(1)

C++

// Author: Huahua, 12 ms

class Solution {

public:

int findKthNumber(int m, int n, int k) {

int l = 1;

int r = m * n + 1;

while (l < r) {

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

if (LEX(m, n, x) >= k)

r = x;

else

l = x + 1;

}

return l;

}

private:

// Returns # of elements in the m*n table that are <= x

int LEX(int m, int n, int x) {

int count = 0;

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

count += min(n, x / i);

return count;

}

};

Java

// Author: Huahua, 16 ms

class Solution {

public int findKthNumber(int m, int n, int k) {

int l = 1;

int r = m * n + 1;

while (l < r) {

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

if (LEX(m, n, x) >= k)

r = x;

else

l = x + 1;

}

return l;

}

// Returns # of elements in the m*n table that are <= x

private int LEX(int m, int n, int x) {

int count = 0;

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

count += Math.min(n, x / i);

return count;

}

Python3

# Author: Huahua, 976 ms

class Solution:

def findKthNumber(self, m, n, k):

def LEX(m, n, x, k):

count = 0

for i in range(1, min(m + 1, x + 1)):

count += min(n, x // i)

if count >= k: return count

return count

l = 1

r = m * n + 1

while l < r:

x = l + (r - l) // 2

if LEX(m, n, x, k) >= k:

r = x

else:

l = x + 1

return l

Problem

We have an array A of non-negative integers.

For every (contiguous) subarray B = [A[i], A[i+1], ..., A[j]] (with i <= j), we take the bitwise OR of all the elements in B, obtaining a result A[i] | A[i+1] | ... | A[j].

Return the number of possible results. (Results that occur more than once are only counted once in the final answer.)

Example 1:

Input: [0]
Output: 1
Explanation: 
There is only one possible result: 0.

Example 2:

Input: [1,1,2]
Output: 3
Explanation: 
The possible subarrays are [1], [1], [2], [1, 1], [1, 2], [1, 1, 2].
These yield the results 1, 1, 2, 1, 3, 3.
There are 3 unique values, so the answer is 3.

Example 3:

Input: [1,2,4]
Output: 6
Explanation: 
The possible results are 1, 2, 3, 4, 6, and 7.

Note:

1 <= A.length <= 50000
0 <= A[i] <= 10^9

Solution 1: DP (TLE)

dp[i][j] := A[i] | A[i + 1] | … | A[j]

dp[i][j] = dp[i][j – 1] | A[j]

ans = len(set(dp))

Time complexity: O(n^2)

Space complexity: O(n^2) -> O(n)

C++ SC O(n^2)

// Author: Huahua

// Running time: TLE (73/83 passed).

class Solution {

public:

int subarrayBitwiseORs(vector<int>& A) {

int n = A.size();

vector<vector<int>> dp(n, vector<int>(n));

unordered_set<int> ans(begin(A), end(A));

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

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

int j = i + l - 1;

if (l == 1) {

dp[i][j] = A[i];

continue;

}

dp[i][j] = dp[i][j - 1] | A[j];

ans.insert(dp[i][j]);

}

return ans.size();

}

};

C++ SC O(n)

// Author: Huahua

// Running time: TLE (75/83 passed)

class Solution {

public:

int subarrayBitwiseORs(vector<int>& A) {

int n = A.size();

vector<int> dp(A);

unordered_set<int> ans(begin(A), end(A));

for (int l = 2; l <= n; ++l)

for (int i = 0; i <= n - l; ++i)

ans.insert(dp[i] |= A[i + l - 1]);

return ans.size();

}

};

Solution 2: DP opted

dp[i] := {A[i], A[i] | A[i – 1], A[i] | A[i – 1] | A[i – 2], … , A[i] | A[i – 1] | … | A[0]}, bitwise ors of all subarrays end with A[i].

|dp[i]| <= 32

Proof: all the elements (in the order of above sequence) in dp[i] are monotonically increasing by flipping 0 bits to 1 from A[i].

There are at most 32 0s in A[i]. Thus the size of the set is <= 32.

证明： dp[i] = {A[i], A[i] | A[i – 1], A[i] | A[i – 1] | A[i – 2], … , A[i] | A[i – 1] | … | A[0]}，这个序列单调递增，通过把A[i]中的0变成1。A[i]最多有32个0。所以这个集合的大小 <= 32。

e.g. 举例：Worst Case 最坏情况 A = [8, 4, 2, 1, 0] A[i] = 2^(n-i)。

A[5] = 0，dp[5] = {0, 0 | 1, 0 | 1 | 2, 0 | 1 | 2 | 4, 0 | 1 | 2 | 4 | 8} = {0, 1, 3, 7, 15}.

Time complexity: O(n*log(max(A))) < O(32n)

Space complexity: O(n*log(max(A)) < O(32n)

C++

// Author: Huahua

// Running time: 456 ms

class Solution {

public:

int subarrayBitwiseORs(vector<int>& A) {

unordered_set<int> ans;

unordered_set<int> cur;

unordered_set<int> nxt;

for (int a : A) {

nxt.clear();

nxt.insert({a});

for (int b : cur) {

nxt.insert(a | b);

}

cur.swap(nxt);

ans.insert(begin(cur), end(cur));

}

return ans.size();

}

};

Java

// Author: Huahua

// Running time: 434 ms

class Solution {

public int subarrayBitwiseORs(int[] A) {

Set<Integer> ans = new HashSet<>();

Set<Integer> cur = new HashSet<>();

for (int a : A) {

Set<Integer> nxt = new HashSet<>();

nxt.add(a);

for (int b : cur)

nxt.add(a | b);

ans.addAll(nxt);

cur = nxt;

}

return ans.size();

}

Python3

# Author: Huahua

# Running time: 812 ms

class Solution:

def subarrayBitwiseORs(self, A):

cur = set()

ans = set()

for a in A:

cur = {a | b for b in cur} | {a}

ans |= cur

return len(ans)

Posts published in September 2018

花花酱 LeetCode 668. Kth Smallest Number in Multiplication Table

Problem

Solution 1: Nth element (MLE)

C++

Solution2 : Binary Search

C++

Java

Python3

Related Problems

花花酱LeetCode 200期总结与展望

[反面教材] 我是如何快速搭建一个公众号机器人的

Bilibili Channel Opened!

花花酱 LeetCode 898. Bitwise ORs of Subarrays

Problem

Solution 1: DP (TLE)

C++ SC O(n^2)

C++ SC O(n)

Solution 2: DP opted

C++

Java

Python3