花花酱 LeetCode 357. Count Numbers with Unique Digits

By zxi on July 16, 2018

Problem

Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10ⁿ.

Example:
Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99])

Solution: Math

f(0) = 1 (0)

f(1) = 10 (0 – 9)

f(2) = 9 * 9 (1-9 * (0 ~ 9 exclude the one from first digit))

f(3) = 9 * 9 * 8

f(4) = 9 * 9 * 8 * 7

…

f(x) = 0 if x >= 10

ans = sum(f[1] ~ f[n])

Time complexity: O(1)

Space complexity: O(1)

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

int countNumbersWithUniqueDigits(int n) {

if (n == 0) return 1;

vector<int> f(11);

f[1] = 10;

f[2] = 9 * 9;

for (int i = 3; i <= 10; ++i)

f[i] = f[i - 1] * (10 - i + 1);

int ans = 0;

for (int i = 0; i <= min(10, n); ++i)

ans += f[i];

return ans;

}

};

花花酱 LeetCode 840. Magic Squares In Grid

By zxi on July 8, 2018

Problem

A 3 x 3 magic square is a 3 x 3 grid filled with distinct numbers from 1 to 9 such that each row, column, and both diagonals all have the same sum.

Given an grid of integers, how many 3 x 3 “magic square” subgrids are there? (Each subgrid is contiguous).

Example 1:

Input: [[4,3,8,4],
        [9,5,1,9],
        [2,7,6,2]]
Output: 1
Explanation: 
The following subgrid is a 3 x 3 magic square:
438
951
276

while this one is not:
384
519
762

In total, there is only one magic square inside the given grid.

Note:

1 <= grid.length <= 10
1 <= grid[0].length <= 10
0 <= grid[i][j] <= 15

Solution

Time complexity: O(m*n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

int numMagicSquaresInside(vector<vector<int>>& grid) {

int m = grid.size();

int n = grid[0].size();

int ans = 0;

for (int i = 0; i < m - 2; ++i)

for (int j = 0; j < n - 2; ++j)

ans += magic(grid, j, i);

return ans;

}

private:

int magic(const vector<vector<int>>& grid, int x, int y) {

vector<int> rows(3);

vector<int> cols(3);

vector<int> exps{15, 15, 15};

int dig = 0;

for (int i = 0; i < 3; ++i)

for (int j = 0; j < 3; ++j) {

int v = grid[y + i][x + j];

if (v <= 0 || v > 9) return 0; // must between 1 and 9

rows[i] += v;

cols[j] += v;

if (i == j) dig += v;

}

return rows == exps && cols == exps && dig == 15;

}

};

花花酱 LeetCode 867. Prime Palindrome

By zxi on July 8, 2018

Problem

Find the smallest prime palindrome greater than or equal to N.

Recall that a number is prime if it’s only divisors are 1 and itself, and it is greater than 1.

For example, 2,3,5,7,11 and 13 are primes.

Recall that a number is a palindrome if it reads the same from left to right as it does from right to left.

For example, 12321 is a palindrome.

Example 1:

Input: 6
Output: 7

Example 2:

Input: 8
Output: 11

Example 3:

Input: 13
Output: 101

Note:

1 <= N <= 10^8
The answer is guaranteed to exist and be less than 2 * 10^8.

Solution: Math

All odd digits palindromes have a factor 11, they are not prime except 11 itself.

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

int primePalindrome(int N) {

if (N <= 2) return 2;

if (N % 2 == 0) ++N;

while (true) {

if (reverse(N) == N && isPrime(N))

return N;

N += 2;

if (N > 11 & (int)log10(N) % 2 == 1)

// 13 -> 101

// 1001 -> 10001

N = pow(10, (int)log10(N) + 1) + 1;

}

return -1;

}

private:

int reverse(int n) {

int r = 0;

while (n) {

r = 10 * r + n % 10;

n /= 10;

}

return r;

}

bool isPrime(int n) {

if (n <= 1) return false;

for (int i = 2; i <= sqrt(n); ++i)

if (n % i == 0) return false;

return true;

}

};

花花酱 LeetCode 441. Arranging Coins

By zxi on July 7, 2018

Problem

You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly kcoins.

Given n, find the total number of full staircase rows that can be formed.

n is a non-negative integer and fits within the range of a 32-bit signed integer.

Example 1:

n = 5

The coins can form the following rows:
¤
¤ ¤
¤ ¤

Because the 3rd row is incomplete, we return 2.

Example 2:

n = 8

The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤

Because the 4th row is incomplete, we return 3.

Solution: Math

Time complexity: O(sqrt(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

int arrangeCoins(int n) {

for (long i = sqrt(n) * 2 + 1; i >= 0; --i)

if (i * (i + 1) / 2 <= n) return i;

return -1;

}

};

Time complexity: O(1)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

int arrangeCoins(int n) {

// x * (1 + x) / 2 <= n

// x^2 + x - 2n <= 0

// x <= (-1 + sqrt(1 + 8n)) / 2

return (-1 + sqrt(1 + static_cast<long>(n) * 8)) / 2;

}

};

花花酱 LeetCode 492. Construct the Rectangle

By zxi on June 2, 2018

Problem

For a web developer, it is very important to know how to design a web page’s size. So, given a specific rectangular web page’s area, your job by now is to design a rectangular web page, whose length L and width W satisfy the following requirements:

1. The area of the rectangular web page you designed must equal to the given target area.

2. The width W should not be larger than the length L, which means L >= W.

3. The difference between length L and width W should be as small as possible.

You need to output the length L and the width W of the web page you designed in sequence.

Example:

Input: 4
Output: [2, 2]
Explanation: The target area is 4, and all the possible ways to construct it are [1,4], [2,2], [4,1]. 
But according to requirement 2, [1,4] is illegal; according to requirement 3,  [4,1] is not optimal compared to [2,2]. So the length L is 2, and the width W is 2.

Note:

The given area won’t exceed 10,000,000 and is a positive integer
The web page’s width and length you designed must be positive integers.

Solution

Time complexity: O(sqrt(n))

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 3 ms (<98.48%)

class Solution {

public:

vector<int> constructRectangle(int area) {

for (int i = sqrt(area); i >= 1; --i)

if (area % i == 0) return {area / i, i};

}

};

Posts tagged as “math”

花花酱 LeetCode 357. Count Numbers with Unique Digits

Problem

Solution: Math

花花酱 LeetCode 840. Magic Squares In Grid

Problem

Solution

花花酱 LeetCode 867. Prime Palindrome

Problem

Solution: Math

花花酱 LeetCode 441. Arranging Coins

Problem

Solution: Math

花花酱 LeetCode 492. Construct the Rectangle

Problem

Solution