Posts tagged as “binary search”

花花酱 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

You are given K eggs, and you have access to a building with N floors from 1 to N.

Each egg is identical in function, and if an egg breaks, you cannot drop it again.

You know that there exists a floor F with 0 <= F <= N such that any egg dropped at a floor higher than F will break, and any egg dropped at or below floor F will not break.

Each move, you may take an egg (if you have an unbroken one) and drop it from any floor X (with 1 <= X <= N).

Your goal is to know with certainty what the value of F is.

What is the minimum number of moves that you need to know with certainty what F is, regardless of the initial value of F?

Example 1:

Input: K = 1, N = 2
Output: 2
Explanation: 
Drop the egg from floor 1.  If it breaks, we know with certainty that F = 0.
Otherwise, drop the egg from floor 2.  If it breaks, we know with certainty that F = 1.
If it didn't break, then we know with certainty F = 2.
Hence, we needed 2 moves in the worst case to know what F is with certainty.

Example 2:

Input: K = 2, N = 6
Output: 3

Example 3:

Input: K = 3, N = 14
Output: 4

Note:

1 <= K <= 100
1 <= N <= 10000

Solution 1: Recursion with Memorization (TLE)

dp[k][n] := min number of moves to test n floors with k eggs.

Base cases:

dp[0][n] = 0 # no eggs left.
dp[1][n] = n # one egg, need to test every floor.

Transition:

dp[k][n] = min(1 + max(dp[k][i – 1], dp[k – 1][n – i])) 1 <= i <= n

Time complexity: O(k*n^2)

Space complexity: O(k*n)

// Author: Huahua

// Running time: TLE (69/121 passed)

class Solution {

public:

int superEggDrop(int K, int N) {

m_ = vector<vector<int>>(K + 1, vector<int>(N + 1, INT_MIN));

return dp(K, N);

}

private:

// m[i][j] := min moves of i eggs and j floors

vector<vector<int>> m_;

int dp(int k, int n) {

if (k <= 0) return 0;

if (k == 1) return n;

if (n <= 1) return n;

if (m_[k][n] != INT_MIN) return m_[k][n];

int ans = INT_MAX;

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

ans = min(ans, 1 + max(dp(k - 1, i - 1), // broken at floor i, need to test i - 1 floors using k - 1 eggs.

dp(k, n - i))); // unbroken at floor i, need to test n - i floors using k eggs.

return m_[k][n] = ans;

}

};

Solution 2: Solution 1 + Binary Search

Time complexity: O(k*n*logn)

Space complexity: O(k*n)

C++

// Author: Huahua

// Running time: 40 ms

class Solution {

public:

int superEggDrop(int K, int N) {

m_ = vector<vector<int>>(K + 1, vector<int>(N + 1, INT_MIN));

return dp(K, N);

}

private:

// m[i][j] := min moves of i eggs and j floors

vector<vector<int>> m_;

int dp(int k, int n) {

if (k <= 0) return 0;

if (k == 1) return n;

if (n <= 1) return n;

if (m_[k][n] != INT_MIN) return m_[k][n];

// broken[i] = dp(k - 1, i - 1) is incresing with i.

// unbroken[i] = dp(k, n - i) is decresing with i.

// dp[k][n] = 1 + min(max(broken[i], unbroken[i])), 1 <= i <= n

// find the smallest i such that broken[i] >= unbroken[i],

// which minimizes max(broken[i], unbroken[i]).

int l = 1;

int r = n + 1;

while (l < r) {

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

int broken = dp(k - 1, m - 1);

int unbroken = dp(k, n - m);

if (broken >= unbroken)

r = m;

else

l = m + 1;

}

return m_[k][n] = 1 + dp(k - 1, l - 1);

}

};

花花酱 SP5 Binary Search

By zxi on August 12, 2018

Template:

Time complexity: O(log(r-l)) * O(f(m) + g(m))

Space complexity: O(1)

"""

Returns the smallest number m such that g(m) is true.

"""

def binary_search(l, r):

while l < r:

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

if f(m): return m # if m is the answer

if g(m):

r = m # new range [l, m)

else

l = m + 1 # new range [m+1, r)

return l # or not found

Slides:

Lower Bound / Upper Bound

#include <iostream>

#include <vector>

using namespace std;

int upper_bound(const vector<int>& A, int val, int l, int r) {

while (l < r) {

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

if (A[m] > val)

r = m;

else

l = m + 1;

}

return l;

}

int lower_bound(const vector<int>& A, int val, int l, int r) {

while (l < r) {

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

if (A[m] >= val)

r = m;

else

l = m + 1;

}

return l;

}

int main() {

vector<int> A{1, 2, 2, 2, 4, 4, 5};

cout << lower_bound(A, 0, 0, A.size()) << endl; // 0

cout << lower_bound(A, 2, 0, A.size()) << endl; // 1

cout << lower_bound(A, 3, 0, A.size()) << endl; // 4

cout << upper_bound(A, 2, 0, A.size()) << endl; // 4

cout << upper_bound(A, 4, 0, A.size()) << endl; // 6

cout << upper_bound(A, 5, 0, A.size()) << endl; // 7

}

Mentioned Problems

花花酱 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_;

};

Posts tagged as “binary search”

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

Problem

Solution 1: Nth element (MLE)

C++

Solution2 : Binary Search

C++

Java

Python3

Related Problems

花花酱 LeetCode 887. Super Egg Drop

Problem

Solution 1: Recursion with Memorization (TLE)

Solution 2: Solution 1 + Binary Search

花花酱 SP5 Binary Search

Mentioned Problems

花花酱 LeetCode 878. Nth Magical Number

Problem

Solution: Math + Binary Search

花花酱 LeetCode 880. Random Pick with Weight

Problem

Solution: Binary Search

Related Problems