Tag Archives: number

Number of Digit One

https://leetcode.com/problems/number-of-digit-one/ Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n. For example: Given n = 13, Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13. Solution. The solution is to iterate each digit. Each time, split… Read More »

Patching Array

Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n] inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required. Example 1: nums = [1, 3], n = 6 Return 1.… Read More »

Strobogrammatic Number II, III

Strobogrammatic Number II A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down). Find all strobogrammatic numbers that are of length = n. For example, Given n = 2, return [“11″,”69″,”88″,”96”]. Solution. The basic idea is to iterate from inside to outside. If n is even, we… Read More »

Digital Root

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit. For example: Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it. Solution. We need to refer to this wiki digital root.… Read More »

Additive Number

https://leetcode.com/problems/additive-number/ Additive number is a string whose digits can form additive sequence. A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two. For example: “112358” is an additive number because the digits can form an… Read More »

pascal triangle

https://leetcode.com/problems/pascals-triangle-ii/ Given an index k, return the kth row of the Pascal’s triangle. For example, given k = 3, Return [1,3,3,1]. Analysis Matrix like below is a pascal triangle p[][]. For row i, column j, p[i][j] it has value C(i, j) [Binomial Coefficient]. Below is the formula which can help us get C(n, m) from… Read More »

Compress URL by base62

Consider we have an URL, and we want to compress it. Base62 way is to find the URL integer id in database, then we transfer the integer id into base62 code. Bascially, it is bijection mapping between [0…9] and [a…zA….Z0…9]. The number of [a…zA….Z0…9] is totally 62. From integer to base62 url, each time, we use integer… Read More »

power(a, n) in iteration way

Given a, n, calculate a^n in non-recursive way. The traditional way is to use recursion to reach O(logN) solution. For iteration, we can use stack to implement the recursion process. In stack, 1 means result times a, -1 means result times result, 0 doing nothing. Take 11 as example, the process is like: Take 15 as… Read More »

Max Gap between consecutive numbers

Source: http://www.careercup.com/question?id=14764703 Given a unsorted array with n elements. How can we find the largest gap between consecutive numbers of sorted version in O(n)? For example, we have a unsorted array 9 19 13 12 33 41 22 the sorted version is 9 12 13 19 22 33 41 the output of the algorithm should be… Read More »