Posts tagged as “math”

花花酱 LeetCode 991. Broken Calculator

By zxi on February 10, 2019

On a broken calculator that has a number showing on its display, we can perform two operations:

Double: Multiply the number on the display by 2, or;
Decrement: Subtract 1 from the number on the display.

Initially, the calculator is displaying the number X.

Return the minimum number of operations needed to display the number Y.

Example 1:

Input: X = 2, Y = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.

Example 2:

Input: X = 5, Y = 8
Output: 2
Explanation: Use decrement and then double {5 -> 4 -> 8}.

Example 3:

Input: X = 3, Y = 10
Output: 3
Explanation:  Use double, decrement and double {3 -> 6 -> 5 -> 10}.

Example 4:

Input: X = 1024, Y = 1
Output: 1023
Explanation: Use decrement operations 1023 times.

Note:

1 <= X <= 10^9
1 <= Y <= 10^9

Solution: Greedy

Thinking backwards, making Y <= X by adding 1 or dividing 2.

If Y is even, (Y + 1) // 2 == Y // 2, there is no need to do the extra step
If Y is odd (Y + 1) // 2 = (Y // 2) + 1, so only do + 1 when Y is odd

Time complexity: O(log(Y-X))
Space complexity: O(1)

C++

// Author: Huahua, running time: 4 ms, 4.7 MB

class Solution {

public:

int brokenCalc(int X, int Y) {

if (X <= Y) return X - Y;

return 1 + brokenCalc(X, Y % 2 ? Y + 1 : Y / 2);

}

};

花花酱 LeetCode 989. Add to Array-Form of Integer

By zxi on February 10, 2019

For a non-negative integer X, the array-form of X is an array of its digits in left to right order. For example, if X = 1231, then the array form is [1,2,3,1].

Given the array-form A of a non-negative integer X, return the array-form of the integer X+K.

Example 1:

Input: A = [1,2,0,0], K = 34
Output: [1,2,3,4]
Explanation: 1200 + 34 = 1234

Example 2:

Input: A = [2,7,4], K = 181
Output: [4,5,5]
Explanation: 274 + 181 = 455

Example 3:

Input: A = [2,1,5], K = 806
Output: [1,0,2,1]
Explanation: 215 + 806 = 1021

Example 4:

Input: A = [9,9,9,9,9,9,9,9,9,9], K = 1
Output: [1,0,0,0,0,0,0,0,0,0,0]
Explanation: 9999999999 + 1 = 10000000000

Note：

1 <= A.length <= 10000
0 <= A[i] <= 9
0 <= K <= 10000
If A.length > 1, then A[0] != 0

Solution: Simulation

Time complexity: O(n) Space complexity: O(n)

C++

// Author: Huahua, running time: 136 ms, 10.1 MB

class Solution {

public:

vector<int> addToArrayForm(vector<int>& A, int K) {

vector<int> ans;

ans.reserve(A.size() + 1);

for (int i = A.size() - 1; i >= 0 || K > 0; --i) {

K += (i >= 0 ? A[i] : 0);

ans.push_back(K % 10);

K /= 10;

}

reverse(begin(ans), end(ans));

return ans;

}

};

花花酱 LeetCode 781. Rabbits in Forest

By zxi on February 9, 2019

In a forest, each rabbit has some color. Some subset of rabbits (possibly all of them) tell you how many other rabbits have the same color as them. Those answers are placed in an array.

Return the minimum number of rabbits that could be in the forest.

Examples:
Input: answers = [1, 1, 2]
Output: 5
Explanation:
The two rabbits that answered "1" could both be the same color, say red.
The rabbit than answered "2" can't be red or the answers would be inconsistent.
Say the rabbit that answered "2" was blue.
Then there should be 2 other blue rabbits in the forest that didn't answer into the array.
The smallest possible number of rabbits in the forest is therefore 5: 3 that answered plus 2 that didn't.

Input: answers = [10, 10, 10]
Output: 11

Input: answers = []
Output: 0

Note:

answers will have length at most 1000.
Each answers[i] will be an integer in the range [0, 999].

Solution: Math

Say there n rabbits answered x.
if n <= x: they can have the same color
if n > x: they must be divided into groups, each group has x + 1 rabbits, and there are at least ceil(n / (x+1)) groups.
So there will be ceil(n / (x + 1)) * (x + 1) rabbits. This expression can be expressed as (n + x) / (x + 1) * (x + 1) in programming languages. (n + x) // (x + 1) * (x + 1) for Python3.

C++

// Author: Huahua, running time: 8 ms / 5.2 MB

class Solution {

public:

int numRabbits(vector<int>& answers) {

vector<int> counts(*max_element(begin(answers), end(answers)) + 1);

for (const int answer : answers)

++counts[answer];

int total = 0;

for (int x = 0; x < counts.size(); ++x)

total += (counts[x] + x) / (x + 1) * (x + 1);

return total;

}

};

Python3

# Author: Huahua, running time: 36 ms / 6.5 MB

class Solution:

def numRabbits(self, answers: 'List[int]') -> 'int':

counts = collections.Counter(answers)

return sum([(n + x) // (x + 1) * (x + 1) for x, n in counts.items()])

花花酱 LeetCode 973. K Closest Points to Origin

By zxi on January 13, 2019

We have a list of points on the plane. Find the K closest points to the origin (0, 0).

(Here, the distance between two points on a plane is the Euclidean distance.)

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in.)

Example 1:

Input: points = [[1,3],[-2,2]], K = 1 
Output: [[-2,2]] 
Explanation:  The distance between (1, 3) and the origin is sqrt(10). The distance between (-2, 2) and the origin is sqrt(8). Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin. We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].

Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], K = 2 
Output: [[3,3],[-2,4]] (The answer [[-2,4],[3,3]] would also be accepted.)

Note:

1 <= K <= points.length <= 10000
-10000 < points[i][0] < 10000
-10000 < points[i][1] < 10000

Solution: Sort

Time complexity: O(nlogn)
Space complexity: O(n)

C++

// Author: Huahua, Running time: 180 ms

class Solution {

public:

vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {

vector<long> s(points.size());

for (int i = 0; i < points.size(); ++i)

s[i] = (static_cast<long>(points[i][0] * points[i][0] +

points[i][1] * points[i][1]) << 32) | i;

std::sort(begin(s), end(s));

vector<vector<int>> ans(K);

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

ans[i] = points[static_cast<int>(s[i])];

return ans;

}

};

Python3

# Author: Huahua, running time: 528 ms

class Solution:

def kClosest(self, points, K):

return sorted(points, key = lambda p: p[0]**2 + p[1]**2)[0:K]

花花酱 LeetCode 972. Equal Rational Numbers

By zxi on January 5, 2019

Given two strings S and T, each of which represents a non-negative rational number, return True if and only if they represent the same number. The strings may use parentheses to denote the repeating part of the rational number.

In general a rational number can be represented using up to three parts: an integer part, a non-repeating part, and a repeating part. The number will be represented in one of the following three ways:

<IntegerPart> (e.g. 0, 12, 123)
<IntegerPart><.><NonRepeatingPart> (e.g. 0.5, 1., 2.12, 2.0001)
<IntegerPart><.><NonRepeatingPart><(><RepeatingPart><)> (e.g. 0.1(6), 0.9(9), 0.00(1212))

The repeating portion of a decimal expansion is conventionally denoted within a pair of round brackets. For example:

1 / 6 = 0.16666666… = 0.1(6) = 0.1666(6) = 0.166(66)

Both 0.1(6) or 0.1666(6) or 0.166(66) are correct representations of 1 / 6.

Example 1:

Input: S = "0.(52)", T = "0.5(25)"
Output: true
Explanation:
Because "0.(52)" represents 0.52525252..., and "0.5(25)" represents 0.52525252525..... , the strings represent the same number.

Example 2:

Input: S = "0.1666(6)", T = "0.166(66)"
Output: true

Example 3:

Input: S = "0.9(9)", T = "1."
Output: true
Explanation: 
"0.9(9)" represents 0.999999999... repeated forever, which equals 1.  [See this link for an explanation.]
"1." represents the number 1, which is formed correctly: (IntegerPart) = "1" and (NonRepeatingPart) = "".

Note:

Each part consists only of digits.
The <IntegerPart> will not begin with 2 or more zeros. (There is no other restriction on the digits of each part.)
1 <= <IntegerPart>.length <= 4
0 <= <NonRepeatingPart>.length <= 4
1 <= <RepeatingPart>.length <= 4

Solution1: Expend the string

Extend the string to 16+ more digits and covert it to double.

0.9(9) => 0.99999999999999
0.(52) => 0.525252525252525
0.5(25) => 0.5252525252525

C++

// Author: Huahua, running time: 4 ms

class Solution {

public:

bool isRationalEqual(string S, string T) {

auto convert = [](string s) {

// 0.1234(567)

// 01234567890

// i = 1, p = 6

auto i = s.find('.');

auto p = s.find('(');

if (p != string::npos) {

string r = s.substr(p + 1, s.length() - p - 2);

s = s.substr(0, p);

while (s.length() < 16)

s += r;

}

return stod(s);

};

return abs(convert(S) - convert(T)) < 1e-10;

}

};

Python3

class Solution:

def isRationalEqual(self, S, T):

def convert(s):

i = s.find('.')

p = s.find('(')

if p >= 0:

r = s[p+1:-1]

s = s[0:p]

while len(s) < 16:

s += r

return float(s)

return abs(convert(S) - convert(T)) < 1e-10

Solution 2: Convert to a friction number

C++

// Author: Huahua, running time: 24 ms.

class Friction {

public:

Friction(long n = 0, long d = 1) {

long g = __gcd(n, d);

n_ = n / g;

d_ = d / g;

}

Friction operator+(const Friction& o) const {

return Friction(n_ * o.d_ + d_ * o.n_, d_ * o.d_);

}

bool operator==(const Friction& o) const {

return this->n_ * o.d_ == this->d_ * o.n_;

}

private:

long n_;

long d_;

};

class Solution {

public:

bool isRationalEqual(string S, string T) {

auto convert = [](string s) {

std::regex re("(\\d+)\\.?(\\d+)?(\\((\\d+)\\))?");

std::smatch matches;

std::regex_match(s, matches, re);

string int_part = matches[1].str();

string nr_part = matches[2].str();

string r_part = matches[4].str();

Friction f(stoi(int_part), 1);

const int base = pow(10, nr_part.length());

if (nr_part.length())

f = f + Friction(stoi(nr_part), base);

if (r_part.length())

f = f + Friction(stoi(r_part), (pow(10, r_part.length()) - 1) * base);

return f;

};

return convert(S) == convert(T);

}

};