Math – Page 22 – Huahua’s Tech Road

花花酱 LeetCode 263. Ugly Number

By zxi on January 7, 2018

题目大意：如果一个数的素数因子只有2，3，5，我们称它为丑数。让你判断一个数是不是丑数。

Problem:

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.

Note that 1 is typically treated as an ugly number.

Idea:

Math

Solution:

C++

// Author: Huahua

// Running time: 9 ms

class Solution {

public:

bool isUgly(int num) {

const vector<int> factors{2, 3, 5};

for (const int factor : factors)

while (num && num % factor == 0) num /= factor;

return num == 1;

}

};

Related Problems:

花花酱 LeetCode 264. Ugly Number II

花花酱 LeetCode 754. Reach a Number

By zxi on January 1, 2018

题目大意：第i时刻可以移动+i,-i单位距离。初始在原点，问最少对少时间可以移动到target坐标。

Problem:

You are standing at position 0 on an infinite number line. There is a goal at position target.

On each move, you can either go left or right. During the n-th move (starting from 1), you take n steps.

Return the minimum number of steps required to reach the destination.

Example 1:

Input: target = 3

Output: 2

Explanation:

On the first move we step from 0 to 1.

On the second step we step from 1 to 3.

Example 2:

Input: target = 2

Output: 3

Explanation:

On the first move we step from 0 to 1.

On the second move we step from 1 to -1.

On the third move we step from -1 to 2.

Note:

target will be a non-zero integer in the range [-10^9, 10^9].

Idea:

Math

Time complexity: O(sqrt(target))

Space complexity: O(1)

// Author: Huahua

// Running time: 3 ms

class Solution {

public:

int reachNumber(int target) {

target = std::abs(target);

int k = 0;

int sum = 0;

while (sum < target) sum += (++k);

const int d = sum - target;

if (d % 2 == 0) return k;

return k + 1 + (k % 2);

}

};

O(1)

// Author: Huahua

// Running time: 3 ms

class Solution {

public:

int reachNumber(int target) {

target = std::abs(target);

int k = sqrt(target * 2);

while (sum(k) < target) ++k;

int d = sum(k) - target;

if (d % 2 == 0) return k;

return k + 1 + (k % 2);

}

private:

int sum(int k) {

return k * (k + 1) / 2;

}

};

花花酱 LeetCode 367. Valid Perfect Square

By zxi on December 29, 2017

题目大意：判断一个数是否是平方数。不能使用开根号函数。

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

Example 1:

1 2	Input: 16 Returns: True

Example 2:

1 2	Input: 14 Returns: False

Idea:

Binary search

Solution:

C++

Time complexity: O(log(num))

Space complexity: O(1)

// Author: Huahua

// Runtime: 0 ms

class Solution {

public:

bool isPerfectSquare(int num) {

long l = 1;

long r = num + 1;

while (l < r) {

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

long t = m * m;

if (t == num)

return true;

else if (t > num)

r = m;

else

l = m + 1;

}

return false;

}

};

花花酱 LeetCode 728. Self Dividing Numbers

By zxi on November 19, 2017

Problem:

A self-dividing number is a number that is divisible by every digit it contains.

For example, 128 is a self-dividing number because 128 % 1 == 0, 128 % 2 == 0, and 128 % 8 == 0.

Also, a self-dividing number is not allowed to contain the digit zero.

Given a lower and upper number bound, output a list of every possible self dividing number, including the bounds if possible.

Example 1:

Input:

left = 1, right = 22

Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]

Note:

The boundaries of each input argument are 1 <= left <= right <= 10000.

Idea:

Brute Force

Time Complexity: O(n)

Space Complexity: O(1)

Solution:

C++

// Author: Huahua

// Runtime: 3 ms

class Solution {

public:

vector<int> selfDividingNumbers(int left, int right) {

vector<int> ans;

for (int n = left; n <= right; ++n) {

int t = n;

bool valid = true;

while (t && valid) {

const int r = t % 10;

if (r == 0 || n % r)

valid = false;

t /= 10;

}

if (valid) ans.push_back(n);

}

return ans;

}

};

String

// Author: Huahua

// Runtime: 6 ms

class Solution {

public:

vector<int> selfDividingNumbers(int left, int right) {

vector<int> ans;

for (int n = left; n <= right; ++n) {

const string t = std::to_string(n);

bool valid = true;

for (const char c : t) {

if (c == '0' || n % (c - '0')) {

valid = false;

break;

}

if (valid) ans.push_back(n);

}

return ans;

}

};

Related Problems:

[解题报告] LeetCode 611. Valid Triangle Number

花花酱 LeetCode 268. Missing Number

By zxi on September 9, 2017

Problem:

Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.

For example,
Given nums = [0, 1, 3] return 2.

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

Idea:

sum / xor

Solution:

// Author: Huahua

class Solution {

public:

// Solution 1: Sum

int missingNumber(vector<int>& nums) {

int n = nums.size();

int x = (0+n)*(n+1)/2 - accumulate(nums.begin(), nums.end(), 0);

return x;

}

// Solution 2: XOR

int missingNumber(vector<int>& nums) {

int n = nums.size();

int x = 0;

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

x = x ^ i ^ nums[i-1];

return x;

}

};

Posts published in “Math”

花花酱 LeetCode 263. Ugly Number

花花酱 LeetCode 754. Reach a Number

花花酱 LeetCode 367. Valid Perfect Square

花花酱 LeetCode 728. Self Dividing Numbers

花花酱 LeetCode 268. Missing Number