Posts tagged as “brute force”

花花酱 LeetCode 2644. Find the Maximum Divisibility Score

By zxi on April 28, 2023

You are given two 0-indexed integer arrays nums and divisors.

The divisibility score of divisors[i] is the number of indices j such that nums[j] is divisible by divisors[i].

Return the integer divisors[i] with the maximum divisibility score. If there is more than one integer with the maximum score, return the minimum of them.

Example 1:

Input: nums = [4,7,9,3,9], divisors = [5,2,3]
Output: 3
Explanation: The divisibility score for every element in divisors is:
The divisibility score of divisors[0] is 0 since no number in nums is divisible by 5.
The divisibility score of divisors[1] is 1 since nums[0] is divisible by 2.
The divisibility score of divisors[2] is 3 since nums[2], nums[3], and nums[4] are divisible by 3.
Since divisors[2] has the maximum divisibility score, we return it.

Example 2:

Input: nums = [20,14,21,10], divisors = [5,7,5]
Output: 5
Explanation: The divisibility score for every element in divisors is:
The divisibility score of divisors[0] is 2 since nums[0] and nums[3] are divisible by 5.
The divisibility score of divisors[1] is 2 since nums[1] and nums[2] are divisible by 7.
The divisibility score of divisors[2] is 2 since nums[0] and nums[3] are divisible by 5.
Since divisors[0], divisors[1], and divisors[2] all have the maximum divisibility score, we return the minimum of them (i.e., divisors[2]).

Example 3:

Input: nums = [12], divisors = [10,16]
Output: 10
Explanation: The divisibility score for every element in divisors is:
The divisibility score of divisors[0] is 0 since no number in nums is divisible by 10.
The divisibility score of divisors[1] is 0 since no number in nums is divisible by 16.
Since divisors[0] and divisors[1] both have the maximum divisibility score, we return the minimum of them (i.e., divisors[0]).

Constraints:

1 <= nums.length, divisors.length <= 1000
1 <= nums[i], divisors[i] <= 10⁹

Solution: Brute Force

Time complexity: O(m*n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int maxDivScore(vector<int>& nums, vector<int>& divisors) {

int maxScore = 0;

int ans = INT_MAX;

for (int d : divisors) {

int score = 0;

for (int x : nums) {

score += x % d == 0;

}

if (score > maxScore) {

maxScore = score;

ans = d;

}

if (score == maxScore)

ans = min(ans, d);

}

return ans;

}

};

花花酱 LeetCode 2249. Count Lattice Points Inside a Circle

By zxi on April 27, 2022

Given a 2D integer array circles where circles[i] = [x_i, y_i, r_i] represents the center (x_i, y_i) and radius r_i of the i^th circle drawn on a grid, return the number of lattice points that are present inside at least one circle.

Note:

A lattice point is a point with integer coordinates.
Points that lie on the circumference of a circle are also considered to be inside it.

Example 1:

Input: circles = [[2,2,1]]
Output: 5
Explanation:
The figure above shows the given circle.
The lattice points present inside the circle are (1, 2), (2, 1), (2, 2), (2, 3), and (3, 2) and are shown in green.
Other points such as (1, 1) and (1, 3), which are shown in red, are not considered inside the circle.
Hence, the number of lattice points present inside at least one circle is 5.

Example 2:

Input: circles = [[2,2,2],[3,4,1]]
Output: 16
Explanation:
The figure above shows the given circles.
There are exactly 16 lattice points which are present inside at least one circle. 
Some of them are (0, 2), (2, 0), (2, 4), (3, 2), and (4, 4).

Constraints:

1 <= circles.length <= 200
circles[i].length == 3
1 <= x_i, y_i <= 100
1 <= r_i <= min(x_i, y_i)

Solution: Brute Force

Time complexity: O(m * m * n) = O(200 * 200 * 200)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int countLatticePoints(vector<vector<int>>& circles) {

auto isIn = [](int u, int v, int x, int y, int r) {

return (u - x) * (u - x) + (v - y) * (v - y) <= r * r;

};

int ans = 0;

for (int u = 0; u <= 200; ++u)

for (int v = 0; v <= 200; ++v) {

bool found = false;

for (const auto& c : circles)

if (isIn(u, v, c[0], c[1], c[2])) {

found = true;

break;

}

ans += found;

}

return ans;

}

};

花花酱 LeetCode 2176. Count Equal and Divisible Pairs in an Array

By zxi on March 4, 2022

Given a 0-indexed integer array nums of length n and an integer k, return the number of pairs(i, j)where0 <= i < j < n, such thatnums[i] == nums[j]and(i * j)is divisible byk.

Example 1:

Input: nums = [3,1,2,2,2,1,3], k = 2
Output: 4
Explanation:
There are 4 pairs that meet all the requirements:
- nums[0] == nums[6], and 0 * 6 == 0, which is divisible by 2.
- nums[2] == nums[3], and 2 * 3 == 6, which is divisible by 2.
- nums[2] == nums[4], and 2 * 4 == 8, which is divisible by 2.
- nums[3] == nums[4], and 3 * 4 == 12, which is divisible by 2.

Example 2:

Input: nums = [1,2,3,4], k = 1
Output: 0
Explanation: Since no value in nums is repeated, there are no pairs (i,j) that meet all the requirements.

Constraints:

1 <= nums.length <= 100
1 <= nums[i], k <= 100

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

int countPairs(vector<int>& nums, int k) {

const int n = nums.size();

int ans = 0;

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

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

ans += (nums[i] == nums[j]) && (i * j % k == 0);

return ans;

}

};

花花酱 LeetCode 1620. Coordinate With Maximum Network Quality

By zxi on October 17, 2020

You are given an array of network towers towers and an integer radius, where towers[i] = [x_i, y_i, q_i] denotes the i^th network tower with location (x_i, y_i) and quality factor q_i. All the coordinates are integral coordinates on the X-Y plane, and the distance between two coordinates is the Euclidean distance.

The integer radius denotes the maximum distance in which the tower is reachable. The tower is reachable if the distance is less than or equal to radius. Outside that distance, the signal becomes garbled, and the tower is not reachable.

The signal quality of the i^th tower at a coordinate (x, y) is calculated with the formula ⌊q_i / (1 + d)⌋, where d is the distance between the tower and the coordinate. The network quality at a coordinate is the sum of the signal qualities from all the reachable towers.

Return the integral coordinate where the network quality is maximum. If there are multiple coordinates with the same network quality, return the lexicographically minimum coordinate.

Note:

A coordinate (x1, y1) is lexicographically smaller than (x2, y2) if either x1 < x2 or x1 == x2 and y1 < y2.
⌊val⌋ is the greatest integer less than or equal to val (the floor function).

Example 1:

Input: towers = [[1,2,5],[2,1,7],[3,1,9]], radius = 2
Output: [2,1]
Explanation: 
At coordinate (2, 1) the total quality is 13
- Quality of 7 from (2, 1) results in ⌊7 / (1 + sqrt(0)⌋ = ⌊7⌋ = 7
- Quality of 5 from (1, 2) results in ⌊5 / (1 + sqrt(2)⌋ = ⌊2.07⌋ = 2
- Quality of 9 from (3, 1) results in ⌊9 / (1 + sqrt(1)⌋ = ⌊4.5⌋ = 4
No other coordinate has higher quality.

Example 2:

Input: towers = [[23,11,21]], radius = 9
Output: [23,11]

Example 3:

Input: towers = [[1,2,13],[2,1,7],[0,1,9]], radius = 2
Output: [1,2]

Example 4:

Input: towers = [[2,1,9],[0,1,9]], radius = 2
Output: [0,1]
Explanation: Both (0, 1) and (2, 1) are optimal in terms of quality but (0, 1) is lexicograpically minimal.

Constraints:

1 <= towers.length <= 50
towers[i].length == 3
0 <= x_i, y_i, q_i <= 50
1 <= radius <= 50

Solution: Brute Force

Try all possible coordinates from (0, 0) to (50, 50).

Time complexity: O(|X|*|Y|*t)
Space complexity: O(1)

C++

class Solution {

public:

vector<int> bestCoordinate(vector<vector<int>>& towers, int radius) {

constexpr int n = 50;

vector<int> ans;

int max_q = 0;

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

for (int y = 0; y <= n; ++y) {

int q = 0;

for (const auto& tower : towers) {

const int tx = tower[0], ty = tower[1];

const float d = sqrt((x - tx) * (x - tx) + (y - ty) * (y - ty));

if (d > radius) continue;

q += floor(tower[2] / (1 + d));

}

if (q > max_q) {

max_q = q;

ans = {x, y};

}

return ans;

}

};

花花酱 LeetCode 1608. Special Array With X Elements Greater Than or Equal X

By zxi on October 4, 2020

You are given an array nums of non-negative integers. nums is considered special if there exists a number x such that there are exactly x numbers in nums that are greater than or equal to x.

Notice that x does not have to be an element in nums.

Return x if the array is special, otherwise, return -1. It can be proven that if nums is special, the value for x is unique.

Example 1:

Input: nums = [3,5]
Output: 2
Explanation: There are 2 values (3 and 5) that are greater than or equal to 2.

Example 2:

Input: nums = [0,0]
Output: -1
Explanation: No numbers fit the criteria for x.
If x = 0, there should be 0 numbers >= x, but there are 2.
If x = 1, there should be 1 number >= x, but there are 0.
If x = 2, there should be 2 numbers >= x, but there are 0.
x cannot be greater since there are only 2 numbers in nums.

Example 3:

Input: nums = [0,4,3,0,4]
Output: 3
Explanation: There are 3 values that are greater than or equal to 3.

Example 4:

Input: nums = [3,6,7,7,0]
Output: -1

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 1000

Solution 1: Brute Force

Try all possible x from 0 to n.

Time complexity: O(n^2)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int specialArray(vector<int>& nums) {

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

if (x == count_if(begin(nums), end(nums), [x](int num) {

return num >= x; }))

return x;

return -1;

}

};

Python3

# Author: Huahua

class Solution:

def specialArray(self, nums: List[int]) -> int:

for x in range(len(nums) + 1):

if x == sum([n >= x for n in nums]): return x

return -1

Solution 2: Counting Sort

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

f[i] := sum(nums >= i)

C++

// Author: Huahua

class Solution {

public:

int specialArray(vector<int>& nums) {

const int n = nums.size();

vector<int> f(n + 2);

for (int v : nums) ++f[min(v, n)];

for (int i = n; i >= 0; --i)

if ((f[i] += f[i + 1]) == i) return i;

return -1;

}

};