Press "Enter" to skip to content

Posts tagged as “easy”

花花酱 LeetCode 2769. Find the Maximum Achievable Number

By zxi on July 11, 2023

You are given two integers, num and t.

An integer x is called achievable if it can become equal to num after applying the following operation no more than t times:

  • Increase or decrease x by 1, and simultaneously increase or decrease num by 1.

Return the maximum possible achievable number. It can be proven that there exists at least one achievable number.

Example 1:

Input: num = 4, t = 1
Output: 6
Explanation: The maximum achievable number is x = 6; it can become equal to num after performing this operation:
1- Decrease x by 1, and increase num by 1. Now, x = 5 and num = 5. 
It can be proven that there is no achievable number larger than 6.

Example 2:

Input: num = 3, t = 2
Output: 7
Explanation: The maximum achievable number is x = 7; after performing these operations, x will equal num: 
1- Decrease x by 1, and increase num by 1. Now, x = 6 and num = 4.
2- Decrease x by 1, and increase num by 1. Now, x = 5 and num = 5.
It can be proven that there is no achievable number larger than 7.

Constraints:

  • 1 <= num, t <= 50

Solution: Greedy

Always decrease x and always increase num, the max achievable number x = num + t * 2

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

C++

花花酱 LeetCode 2667. Create Hello World Function

By zxi on May 7, 2023

Write a function createHelloWorld. It should return a new function that always returns "Hello World".

Example 1:

Input: args = []
Output: "Hello World"
Explanation:
const f = createHelloWorld();
f(); // "Hello World"
The function returned by createHelloWorld should always return "Hello World".

Example 2:

Input: args = [{},null,42]
Output: "Hello World"
Explanation:
const f = createHelloWorld();
f({}, null, 42); // "Hello World"
Any arguments could be passed to the function but it should still always return "Hello World".

Constraints:

  • 0 <= args.length <= 10

Solution:

JavaScript

花花酱 LeetCode 2660. Determine the Winner of a Bowling Game

By zxi on April 30, 2023

You are given two 0-indexed integer arrays player1 and player2, that represent the number of pins that player 1 and player 2 hit in a bowling game, respectively.

The bowling game consists of n turns, and the number of pins in each turn is exactly 10.

Assume a player hit xi pins in the ith turn. The value of the ith turn for the player is:

  • 2xi if the player hit 10 pins in any of the previous two turns.
  • Otherwise, It is xi.

The score of the player is the sum of the values of their n turns.

Return

  • 1 if the score of player 1 is more than the score of player 2,
  • 2 if the score of player 2 is more than the score of player 1, and
  • 0 in case of a draw.

Example 1:

Input: player1 = [4,10,7,9], player2 = [6,5,2,3]
Output: 1
Explanation: The score of player1 is 4 + 10 + 2*7 + 2*9 = 46.
The score of player2 is 6 + 5 + 2 + 3 = 16.
Score of player1 is more than the score of player2, so, player1 is the winner, and the answer is 1.

Example 2:

Input: player1 = [3,5,7,6], player2 = [8,10,10,2]
Output: 2
Explanation: The score of player1 is 3 + 5 + 7 + 6 = 21.
The score of player2 is 8 + 10 + 2*10 + 2*2 = 42.
Score of player2 is more than the score of player1, so, player2 is the winner, and the answer is 2.

Example 3:

Input: player1 = [2,3], player2 = [4,1]
Output: 0
Explanation: The score of player1 is 2 + 3 = 5
The score of player2 is 4 + 1 = 5
The score of player1 equals to the score of player2, so, there is a draw, and the answer is 0.

Constraints:

  • n == player1.length == player2.length
  • 1 <= n <= 1000
  • 0 <= player1[i], player2[i] <= 10

Solution: Simulation

We can write a function to compute the score of a player.

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

C++

花花酱 LeetCode 2656. Maximum Sum With Exactly K Elements

By zxi on April 30, 2023

You are given a 0-indexed integer array nums and an integer k. Your task is to perform the following operation exactly k times in order to maximize your score:

  1. Select an element m from nums.
  2. Remove the selected element m from the array.
  3. Add a new element with a value of m + 1 to the array.
  4. Increase your score by m.

Return the maximum score you can achieve after performing the operation exactly k times.

Example 1:

Input: nums = [1,2,3,4,5], k = 3
Output: 18
Explanation: We need to choose exactly 3 elements from nums to maximize the sum.
For the first iteration, we choose 5. Then sum is 5 and nums = [1,2,3,4,6]
For the second iteration, we choose 6. Then sum is 5 + 6 and nums = [1,2,3,4,7]
For the third iteration, we choose 7. Then sum is 5 + 6 + 7 = 18 and nums = [1,2,3,4,8]
So, we will return 18.
It can be proven, that 18 is the maximum answer that we can achieve.

Example 2:

Input: nums = [5,5,5], k = 2
Output: 11
Explanation: We need to choose exactly 2 elements from nums to maximize the sum.
For the first iteration, we choose 5. Then sum is 5 and nums = [5,5,6]
For the second iteration, we choose 6. Then sum is 5 + 6 = 11 and nums = [5,5,7]
So, we will return 11.
It can be proven, that 11 is the maximum answer that we can achieve.

Constraints:

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

Solution: Greedy

Always to chose the largest element from the array.

We can find the largest element of the array m, then the total score will be
m + (m + 1) + (m + 2) + … + (m + k – 1),
We can use summation formula of arithmetic sequence to compute that in O(1)
ans = (m + (m + k – 1)) * k / 2

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

C++

花花酱 LeetCode 2639. Find the Width of Columns of a Grid

By zxi on April 29, 2023

You are given a 0-indexed m x n integer matrix grid. The width of a column is the maximum length of its integers.

  • For example, if grid = [[-10], [3], [12]], the width of the only column is 3 since -10 is of length 3.

Return an integer array ans of size n where ans[i] is the width of the ith column.

The length of an integer x with len digits is equal to len if x is non-negative, and len + 1 otherwise.

Example 1:

Input: grid = [[1],[22],[333]]
Output: [3]
Explanation: In the 0th column, 333 is of length 3.

Example 2:

Input: grid = [[-15,1,3],[15,7,12],[5,6,-2]]
Output: [3,1,2]
Explanation: 
In the 0th column, only -15 is of length 3.
In the 1st column, all integers are of length 1. 
In the 2nd column, both 12 and -2 are of length 2.

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 100
  • -109 <= grid[r][c] <= 109

Solution: Simulation

Note: width of ‘0’ is 1.

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

C++