# Posts tagged as “easy”

An ant is on a boundary. It sometimes goes left and sometimes right.

You are given an array of non-zero integers nums. The ant starts reading nums from the first element of it to its end. At each step, it moves according to the value of the current element:

• If nums[i] < 0, it moves left by -nums[i] units.
• If nums[i] > 0, it moves right by nums[i] units.

Return the number of times the ant returns to the boundary.

Notes:

• There is an infinite space on both sides of the boundary.
• We check whether the ant is on the boundary only after it has moved |nums[i]| units. In other words, if the ant crosses the boundary during its movement, it does not count.

Example 1:

Input: nums = [2,3,-5]
Output: 1
Explanation: After the first step, the ant is 2 steps to the right of the boundary.
After the second step, the ant is 5 steps to the right of the boundary.
After the third step, the ant is on the boundary.


Example 2:

Input: nums = [3,2,-3,-4]
Output: 0
Explanation: After the first step, the ant is 3 steps to the right of the boundary.
After the second step, the ant is 5 steps to the right of the boundary.
After the third step, the ant is 2 steps to the right of the boundary.
After the fourth step, the ant is 2 steps to the left of the boundary.
The ant never returned to the boundary, so the answer is 0.


Constraints:

• 1 <= nums.length <= 100
• -10 <= nums[i] <= 10
• nums[i] != 0

## Solution: Simulation

Simulate the position of the ant by summing up the numbers. If the position is zero (at boundary), increase the answer by 1.

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

## C++

You are given an array nums consisting of positive integers.

Return the total frequencies of elements in nums such that those elements all have the maximum frequency.

The frequency of an element is the number of occurrences of that element in the array.

Example 1:

Input: nums = [1,2,2,3,1,4]
Output: 4
Explanation: The elements 1 and 2 have a frequency of 2 which is the maximum frequency in the array.
So the number of elements in the array with maximum frequency is 4.


Example 2:

Input: nums = [1,2,3,4,5]
Output: 5
Explanation: All elements of the array have a frequency of 1 which is the maximum.
So the number of elements in the array with maximum frequency is 5.


Constraints:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100

## Solution: Hashtable

Use a hashtable to store the frequency of each element, and compare it with a running maximum frequency. Reset answer if current frequency is greater than maximum frequency. Increment the answer if current frequency is equal to the maximum frequency.

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

## C++

// Author: Huahua

Given an array of strings words and a string s, determine if s is an acronym of words.

The string s is considered an acronym of words if it can be formed by concatenating the first character of each string in words in order. For example, "ab" can be formed from ["apple", "banana"], but it can’t be formed from ["bear", "aardvark"].

Return true if s is an acronym of words, and false otherwise.

Example 1:

Input: words = ["alice","bob","charlie"], s = "abc"
Output: true
Explanation: The first character in the words "alice", "bob", and "charlie" are 'a', 'b', and 'c', respectively. Hence, s = "abc" is the acronym.


Example 2:

Input: words = ["an","apple"], s = "a"
Output: false
Explanation: The first character in the words "an" and "apple" are 'a' and 'a', respectively.
The acronym formed by concatenating these characters is "aa".
Hence, s = "a" is not the acronym.


Example 3:

Input: words = ["never","gonna","give","up","on","you"], s = "ngguoy"
Output: true
Explanation: By concatenating the first character of the words in the array, we get the string "ngguoy".
Hence, s = "ngguoy" is the acronym.


Constraints:

• 1 <= words.length <= 100
• 1 <= words[i].length <= 10
• 1 <= s.length <= 100
• words[i] and s consist of lowercase English letters.

## Solution: Check the first letter of each word

No need to concatenate, just check the first letter of each word.

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

## C++

Given a 0-indexed integer array nums of length n and an integer target, return the number of pairs(i, j)where0 <= i < j < nandnums[i] + nums[j] < target.

Example 1:

Input: nums = [-1,1,2,3,1], target = 2
Output: 3
Explanation: There are 3 pairs of indices that satisfy the conditions in the statement:
- (0, 1) since 0 < 1 and nums[0] + nums[1] = 0 < target
- (0, 2) since 0 < 2 and nums[0] + nums[2] = 1 < target
- (0, 4) since 0 < 4 and nums[0] + nums[4] = 0 < target
Note that (0, 3) is not counted since nums[0] + nums[3] is not strictly less than the target.


Example 2:

Input: nums = [-6,2,5,-2,-7,-1,3], target = -2
Output: 10
Explanation: There are 10 pairs of indices that satisfy the conditions in the statement:
- (0, 1) since 0 < 1 and nums[0] + nums[1] = -4 < target
- (0, 3) since 0 < 3 and nums[0] + nums[3] = -8 < target
- (0, 4) since 0 < 4 and nums[0] + nums[4] = -13 < target
- (0, 5) since 0 < 5 and nums[0] + nums[5] = -7 < target
- (0, 6) since 0 < 6 and nums[0] + nums[6] = -3 < target
- (1, 4) since 1 < 4 and nums[1] + nums[4] = -5 < target
- (3, 4) since 3 < 4 and nums[3] + nums[4] = -9 < target
- (3, 5) since 3 < 5 and nums[3] + nums[5] = -3 < target
- (4, 5) since 4 < 5 and nums[4] + nums[5] = -8 < target
- (4, 6) since 4 < 6 and nums[4] + nums[6] = -4 < target


Constraints:

• 1 <= nums.length == n <= 50
• -50 <= nums[i], target <= 50

## Solution 1: Brute force

Enumerate all pairs.

Time complexity: O(n2)
Space complexity: O(1)

## Solution 2: Two Pointers

Sort the numbers.

Use two pointers i, and j.
Set i to 0 and j to n – 1.
while (nums[i] + nums[j] >= target) –j
then we have nums[i] + nums[k] < target (i < k <= j), in total (j – i) pairs.
++i, move to the next starting number.
Time complexity: O(nlogn + n)
Space complexity: O(1)

## C++

You are given a 0-indexed integer array nums. You have to find the maximum sum of a pair of numbers from nums such that the maximum digit in both numbers are equal.

Return the maximum sum or -1 if no such pair exists.

Example 1:

Input: nums = [51,71,17,24,42]
Output: 88
Explanation:
For i = 1 and j = 2, nums[i] and nums[j] have equal maximum digits with a pair sum of 71 + 17 = 88.
For i = 3 and j = 4, nums[i] and nums[j] have equal maximum digits with a pair sum of 24 + 42 = 66.
It can be shown that there are no other pairs with equal maximum digits, so the answer is 88.

Example 2:

Input: nums = [1,2,3,4]
Output: -1
Explanation: No pair exists in nums with equal maximum digits.


Constraints:

• 2 <= nums.length <= 100
• 1 <= nums[i] <= 104

## Solution: Brute Force

Enumerate all pairs of nums and check their sum and max digit.

Time complexity: O(n2)
Space complexity: O(1)