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

}

};

花花酱 LeetCode 810. Chalkboard XOR Game

By zxi on May 2, 2018

Problem

We are given non-negative integers nums[i] which are written on a chalkboard. Alice and Bob take turns erasing exactly one number from the chalkboard, with Alice starting first. If erasing a number causes the bitwise XOR of all the elements of the chalkboard to become 0, then that player loses. (Also, we’ll say the bitwise XOR of one element is that element itself, and the bitwise XOR of no elements is 0.)

Also, if any player starts their turn with the bitwise XOR of all the elements of the chalkboard equal to 0, then that player wins.

Return True if and only if Alice wins the game, assuming both players play optimally.

Example:
Input: nums = [1, 1, 2]
Output: false
Explanation: 
Alice has two choices: erase 1 or erase 2. 
If she erases 1, the nums array becomes [1, 2]. The bitwise XOR of all the elements of the chalkboard is 1 XOR 2 = 3. Now Bob can remove any element he wants, because Alice will be the one to erase the last element and she will lose. 
If Alice erases 2 first, now nums becomes [1, 1]. The bitwise XOR of all the elements of the chalkboard is 1 XOR 1 = 0. Alice will lose.

Notes:

1 <= N <= 1000.
0 <= nums[i] <= 2^16.

Solution: Math

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

// Running time: 15 ms

class Solution {

public:

bool xorGame(vector<int>& nums) {

if (nums.size() % 2 == 0) return true;

int x = 0;

for (int num : nums) x ^= num;

return x == 0;

}

};

花花酱 LeetCode 812. Largest Triangle Area

By zxi on April 8, 2018

Problem

题目大意：给你一些点，求用这些点能够成的最大的三角形面积是多少？

https://leetcode.com/problems/largest-triangle-area/description/

You have a list of points in the plane. Return the area of the largest triangle that can be formed by any 3 of the points.

Example:
Input: points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
Output: 2
Explanation: 
The five points are show in the figure below. The red triangle is the largest.

Notes:

3 <= points.length <= 50.
No points will be duplicated.
-50 <= points[i][j] <= 50.
Answers within 10^-6 of the true value will be accepted as correct.

Solution: Brute Force

Time complexity: O(n^3)

Space complexity: O(1)

// Author: Huahua

// Running time: 11 ms

class Solution {

public:

double largestTriangleArea(vector<vector<int>>& points) {

const int n = points.size();

double best = 0.0;

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

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

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

const double a = dist(points[i], points[j]);

const double b = dist(points[i], points[k]);

const double c = dist(points[j], points[k]);

const double s = (a + b + c) / 2;

const double area = sqrt(s * (s - a) * (s - b) * (s - c));

best = max(best, area);

}

return best;

}

private:

static inline double dist(const vector<int>& p1, const vector<int>& p2) {

return sqrt((p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]));

}

};

Posts tagged as “math”

花花酱 LeetCode 867. Prime Palindrome

Problem

Solution: Math

花花酱 LeetCode 441. Arranging Coins

Problem

Solution: Math

花花酱 LeetCode 492. Construct the Rectangle

Problem

Solution

花花酱 LeetCode 810. Chalkboard XOR Game

Problem

Solution: Math

花花酱 LeetCode 812. Largest Triangle Area

Problem

Solution: Brute Force