Press "Enter" to skip to content

Posts published in “Binary Search”

花花酱 LeetCode 793. Preimage Size of Factorial Zeroes Function

Let f(x) be the number of zeroes at the end of x!. (Recall that x! = 1 * 2 * 3 * ... * x, and by convention, 0! = 1.)

For example, f(3) = 0 because 3! = 6 has no zeroes at the end, while f(11) = 2 because 11! = 39916800 has 2 zeroes at the end. Given K, find how many non-negative integers x have the property that f(x) = K.

Note:

  • K will be an integer in the range [0, 10^9].

Idea:

First we need to compute how many trailing zeros n! has.

See  花花酱 LeetCode 172. Factorial Trailing Zeroes for details

It’s hard to say how many numbers have trailing zeros equals to K, but we can find the largest number p whose trailing zeros is K using binary search. (p+1)! has more than K trailing zeros. And do the same thing to find the largest number q whose trailing zeros is K – 1 using binary search.

Then we know that are exact p numbers 1,2,…,p whose trailing zeros are less or equal to K.

And exact q numbers 1, 2, …, q whose trailing zeros are less or equal to K – 1.

q + 1, q + 2, …, m (m – q numbers in total) the numbers with trailing zeros equal to K.

Solution 1: Math + Binary Search

Time complexity: O(log2(INT_MAX)*log5(INT_MAX))

Space complexity: O(1)

C++

 

花花酱 LeetCode 792. Number of Matching Subsequences

题目大意:给你一些单词,问有多少单词出现在字符串S的子序列中。

https://leetcode.com/problems/number-of-matching-subsequences/description/

Given string S and a dictionary of words words, find the number of words[i] that is a subsequence of S.

Note:

  • All words in words and S will only consists of lowercase letters.
  • The length of S will be in the range of [1, 50000].
  • The length of words will be in the range of [1, 5000].
  • The length of words[i] will be in the range of [1, 50].

Solution 1: Brute Force

Time complexity: O((S + L) * W)

C++ w/o cache TLE

Space complexity: O(1)

C++ w/ cache 155 ms

Space complexity: O(W * L)

Solution 2: Indexing+ Binary Search

Time complexity: O(S + W * L * log(S))

Space complexity: O(S)

S: length of S

W: number of words

L: length of a word

C++

Java

 

Python 3:

w/o cache

w/ cache

 

花花酱 LeetCode 378. Kth Smallest Element in a Sorted Matrix

题目大意:给你一个矩阵,每行每列各自排序。找出矩阵中第K小的元素。

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

Note: 
You may assume k is always valid, 1 ≤ k ≤ n2.

Solution 1: Binary Search

Find the smallest x, such that there are k elements that are smaller or equal to x.

Time complexity: O(nlogn*log(max – min))

Space complexity: O(1)

C++

 

花花酱 LeetCode. 69 Sqrt(x)

题目大意:让你实现开根号函数,只需要返回整数部分。

Problem:

Implement int sqrt(int x).

Compute and return the square root of x.

x is guaranteed to be a non-negative integer.

Example 1:

Example 2:

 

 

Solution 1: Brute force

Time complexity: sqrt(x)

C++

C++ div

Java

Python3 TLE

Solution 2: Binary search

Time complexity: O(logn)

C++

Java

Python3

Solution 3: Newton’s method

C++ / float

C++ / int

Java

Python3

花花酱 LeetCode 167. Two Sum II – Input array is sorted

题目大意:给你一个排过序的数组,让你输出两个数的index,他们的和等于target。

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution and you may not use the same element twice.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Solution:

C++ / two pointers

Time complexity: O(n)

Space complexity: O(1)

 

C++ / Binary search

Related Problems: