花花酱 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 507. Perfect Number

By zxi on March 22, 2018

Problem

题目大意：判断一个数的因数和是不是等于它本身。

https://leetcode.com/problems/perfect-number/description/

We define the Perfect Number is a positive integer that is equal to the sum of all its positive divisors except itself.

Now, given an integer n, write a function that returns true when it is a perfect number and false when it is not.

Example:

Input: 28
Output: True
Explanation: 28 = 1 + 2 + 4 + 7 + 14

Note: The input number n will not exceed 100,000,000. (1e8)

Solution: Brute Force

Try allnumbers from 1 to n – 1.

Time complexity: O(n) TLE for prime numbers

Space complexity: O(1)

Solution: Math

Try all numbers from 2 to sqrt(n).

If number i is a divisor of n then n/i is another one.

Be careful about the case when i == n/i, only one should be added to the sum.

Time complexity: O(sqrt(n))

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

bool checkPerfectNumber(int num) {

if (num <= 1) return false;

int sum = 1;

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

if (num % i == 0) sum += i + ((i == num / i) ? 0 : num / i);

return sum == num;

}

};

花花酱 LeetCode. 69 Sqrt(x)

By zxi on January 16, 2018

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

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:

1 2	Input: 4 Output: 2

Example 2:

Input: 8

Output: 2

Explanation: The square root of 8 is 2.82842...

Solution 1: Brute force

Time complexity: sqrt(x)

C++

// Author: Huahua

// Running time: 40 ms

class Solution {

public:

int mySqrt(int x) {

if (x <= 1) return x;

for (long long s = 1; s <= x; ++s)

if (s * s > x) return s - 1;

return -1;

}

};

C++ div

// Author: Huahua

// Running time: 162 ms

class Solution {

public:

int mySqrt(int x) {

if (x <= 1) return x;

for (int s = 1; s <= x; ++s)

if (s > x / s) return s - 1;

return -1;

}

};

Java

// Author: Huahua

// Running time: 71 ms

class Solution {

public int mySqrt(int x) {

if (x <= 1) return x;

for (long s = 1; s <= x; ++s)

if (s * s > x) return (int)s - 1;

return -1;

}

Python3 TLE

"""

Author: Huahua

TLE: 602 / 1017 test cases passed.

"""

class Solution:

def mySqrt(self, x):

if x <= 1: return x

s = 1

while True:

if s*s > x: return s - 1

s += 1

return -1

Solution 2: Binary search

Time complexity: O(logn)

C++

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

int mySqrt(int x) {

long l = 1;

long r = static_cast<long>(x) + 1;

while (l < r) {

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

if (m * m > x) {

r = m;

} else {

l = m + 1;

}

// l: smallest number such that l * l > x

return l - 1;

}

};

Java

// Author: Huahua

// Running time: 47 ms

class Solution {

public int mySqrt(int x) {

int l = 1;

int r = x;

while (l <= r) {

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

if (m > x / m) {

r = m - 1;

} else {

l = m + 1;

}

return r;

}

Python3

"""

Author: Huahua

Running time: 119 ms

"""

class Solution:

def mySqrt(self, a):

l = 1

r = a

while l <= r:

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

if m * m > a:

r = m - 1

else:

l = m + 1

return r;

Solution 3: Newton’s method

C++ / float

// Author: Huahua

// Running time: 28 ms

class Solution {

public:

int mySqrt(int a) {

constexpr double epsilon = 1e-2;

double x = a;

while (x * x - a > epsilon) {

x = (x + a / x) / 2.0;

}

return x;

}

};

C++ / int

// Author: Huahua

// Running time: 27 ms

class Solution {

public:

int mySqrt(int a) {

// f(x) = x^2 - a, find root of f(x)

// Newton's method

// f'(x) = 2x

// x' = x - f(x) / f'(x) = x - (1/2*x - a/(2*x))

// = (x + a / x) / 2

int x = a;

while (x > a / x)

x = (x + a / x) / 2;

return x;

}

};

Java

// Author: Huahua

// Running time: 44 ms

class Solution {

public int mySqrt(int a) {

long x = a;

while (x * x > a)

x = (x + a / x) / 2;

return (int)x;

}

Python3

"""

Author: Huahua

Running time: 100 ms

"""

class Solution:

def mySqrt(self, a):

x = a

while x * x > a:

x = (x + a // x) // 2

return x

花花酱 LeetCode 204. Count Primes

By zxi on September 9, 2017

Problem:

Count the number of prime numbers less than a non-negative number, n.

Idea:

Sieve of Eratosthenes

Time Complexity:

O(nloglogn)

Space Complexity:

O(n)

Solution:

C++

// Author: Huahua

class Solution {

public:

int countPrimes(int n) {

if (n < 3) return 0;

vector<unsigned char> f(n, 1);

f[0] = f[1] = 0;

for(long i=2;i<=sqrt(n);++i) {

if(!f[i]) continue;

for(long j=i*i;j<n;j+=i)

f[j] = 0;

}

int ans = accumulate(f.begin(), f.end(), 0);

return ans;

}

};

Java

// Author: Huahua

// Running time: 16 ms

class Solution {

public int countPrimes(int n) {

int ans = 0;

boolean[] isPrime = new boolean[n + 1];

Arrays.fill(isPrime, true);

isPrime[0] = false;

if (n > 0) isPrime[1] = false;

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

if (!isPrime[i]) continue;

++ans;

for (int j = 2 * i; j < n; j += i)

isPrime[j] = false;

}

return ans;

}

Python3

"""

Author: Huahua

Running time: 800 ms

"""

class Solution:

def countPrimes(self, n):

if n < 3: return 0

isPrime = [True] * (n + 1)

isPrime[0] = False

isPrime[1] = False

ans = 0

for i in range(2, n):

if not isPrime[i]: continue

ans += 1

for j in range(2 * i, n, i):

isPrime[j] = False

return ans

Posts tagged as “sqrt”

花花酱 LeetCode 492. Construct the Rectangle

Problem

Solution

花花酱 LeetCode 507. Perfect Number

Problem

Solution: Brute Force

Solution: Math

花花酱 LeetCode. 69 Sqrt(x)

Solution 1: Brute force

C++

C++ div

Java

Python3 TLE

Solution 2: Binary search

C++

Java

Python3

Solution 3: Newton’s method

C++ / float

C++ / int

Java

Python3

花花酱 LeetCode 204. Count Primes