-
Notifications
You must be signed in to change notification settings - Fork 0
/
1887-reductionOperationsNeeded.ts
70 lines (51 loc) · 2.41 KB
/
1887-reductionOperationsNeeded.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
// ---------------- LEETCODE TASK DESCRIPTION ----------------- //
// ------------ 1887 - REDUCTION OPERATIONS NEEDED ------------ //
/* Given an integer array nums, your goal is to make all elements in nums equal. To complete one operation, follow these steps:
Find the largest value in nums. Let its index be i (0-indexed) and its value be largest. If there are multiple elements with the largest value, pick the smallest i.
Find the next largest value in nums strictly smaller than largest. Let its value be nextLargest.
Reduce nums[i] to nextLargest.
Return the number of operations to make all elements in nums equal.
Example 1:
Input: nums = [5,1,3]
Output: 3
Explanation: It takes 3 operations to make all elements in nums equal:
1. largest = 5 at index 0. nextLargest = 3. Reduce nums[0] to 3. nums = [3,1,3].
2. largest = 3 at index 0. nextLargest = 1. Reduce nums[0] to 1. nums = [1,1,3].
3. largest = 3 at index 2. nextLargest = 1. Reduce nums[2] to 1. nums = [1,1,1].
Example 2:
Input: nums = [1,1,1]
Output: 0
Explanation: All elements in nums are already equal.
Example 3:
Input: nums = [1,1,2,2,3]
Output: 4
Explanation: It takes 4 operations to make all elements in nums equal:
1. largest = 3 at index 4. nextLargest = 2. Reduce nums[4] to 2. nums = [1,1,2,2,2].
2. largest = 2 at index 2. nextLargest = 1. Reduce nums[2] to 1. nums = [1,1,1,2,2].
3. largest = 2 at index 3. nextLargest = 1. Reduce nums[3] to 1. nums = [1,1,1,1,2].
4. largest = 2 at index 4. nextLargest = 1. Reduce nums[4] to 1. nums = [1,1,1,1,1]. */
// ------------------------ SOLUTION -------------------------- //
// Sort the array.
// Iterate through the array from the end.
// If the current number is smaller than the previous number, add the difference to the answer.
// Return the answer.
// Time complexity: O(n log n)
// Space complexity: O(1)
const reductionOperations = (nums: number[]): number => {
if (new Set(nums).size === 1) return 0
nums.sort((a,b) => a - b)
let length = nums.length
let op = 0
for (let i = length -1; i >= 0; i-- ) {
if (nums[i-1] < nums[i]) {
op += length - i
}
}
return op
};
// --------------------------- LOGS --------------------------- //
console.log(reductionOperations([5,1,3]))
console.log(reductionOperations([1,1,1]))
console.log(reductionOperations([1,1,2,2,3]))
// ----------------------- CLI COMMAND ------------------------ //
//run ts-node 1887-reductionOperationsNeeded.ts