Monthly Archives: March 2025
C# || How To Find Minimum Replacements To Sort Array Using C#
The following is a module with functions which demonstrates how to find minimum replacements to sort the array using C#.
1. Minimum Replacements to Sort the Array – Problem Statement
You are given a 0-indexed integer array nums. In one operation you can replace any element of the array with any two elements that sum to it.
- For example, consider nums = [5,6,7]. In one operation, we can replace nums[1] with 2 and 4 and convert nums to [5,2,4,7].
Return the minimum number of operations to make an array that is sorted in non-decreasing order.
Example 1:
Input: nums = [3,9,3]
Output: 2
Explanation: Here are the steps to sort the array in non-decreasing order:
- From [3,9,3], replace the 9 with 3 and 6 so the array becomes [3,3,6,3]
- From [3,3,6,3], replace the 6 with 3 and 3 so the array becomes [3,3,3,3,3]
There are 2 steps to sort the array in non-decreasing order. Therefore, we return 2.
Example 2:
Input: nums = [1,2,3,4,5]
Output: 0
Explanation: The array is already in non-decreasing order. Therefore, we return 0.
2. Minimum Replacements to Sort the Array – Solution
The following is a solution which demonstrates how to find minimum replacements to sort the array.
|
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 |
// ============================================================================ // Author: Kenneth Perkins // Date: Mar 1, 2025 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to find minimum replacements to sort array // ============================================================================ public class Solution { public long MinimumReplacement(int[] nums) { long answer = 0; int n = nums.Length; // Start from the second last element, as the last one is always sorted. for (int i = n - 2; i >= 0; i--) { // No need to break if they are already in order. if (nums[i] <= nums[i + 1]) { continue; } // Count how many elements are made from breaking nums[i]. long numElements = (long)(nums[i] + nums[i + 1] - 1) / (long)nums[i + 1]; // It requires numElements - 1 replacement operations. answer += numElements - 1; // Maximize nums[i] after replacement. nums[i] = nums[i] / (int)numElements; } return answer; } }// http://programmingnotes.org/ |
QUICK NOTES:
The highlighted lines are sections of interest to look out for.
The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.
Once compiled, you should get this as your output for the example cases:
2
0
Hi, I'm a software engineer. I write articles about programming and design in my spare time.
