Given an array of arr[] of N integers, the task is to find the minimum number of moves to sort the array in non-decreasing order by splitting any array element into two parts such that the sum of the parts is the same as that element.
Examples:
Input: arr[] = {3, 4, 2}
Output: 2
Explanation: The moves are:
Split 4 into two parts {2, 2}. Array becomes arr[] = {3, 2, 2, 2}
Split 3 into two parts {1, 2}. Array becomes arr[] = {1, 2, 2, 2, 2}Input: arr[] = {3, 2, 4}
Output: 1
Explanation: Split 3 into two parts {1, 2}. [3, 2, 4] -> [1, 2, 2, 4]
Approach: The solution of the problem is based on the following observation:
As there is need to minimize the operations so keep the rightmost elements as large as possible, i.e., don’t split it.
To minimize operations, split a number into numbers as large as possible and as close to the element just right to it.
Follow the steps mentioned below to solve this problem:
- Traverse from the rightmost element of the array i = N-2 to 0.
- Split the array element into two parts as large as possible and not exceeding the element just at the right and increment the count of split.
- Continue this till the values obtained from splitting arr[i] is not less than the minimum value obtained just at its right.
- Update the minimum value obtained in this process.
- Return the total count of split as the answer.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>#include <vector>using namespace std;// Function to find the minimum// number of splitint minimumSplits(vector<int> arr){ int totalSplits = 0; // Get the value at the last index int prevVal = arr.back(); for (int idx = arr.size() - 2; idx >= 0; idx--) { totalSplits += (arr[idx] - 1) / prevVal; int numGroups = ((arr[idx] - 1) / prevVal + 1); prevVal = arr[idx] / numGroups; } return totalSplits;}// Driver Codeint main(){ vector<int> arr{ 3, 2, 4 }; // Function call int minSplit = minimumSplits(arr); cout << minSplit << endl; return 0;} |
Java
// Java code to implement the approachimport java.lang.*;import java.util.*;class GFG { // Function to count the minimum // number of splits public static int minimumSplits(int arr[], int n) { int totalSplits = 0; // Get the value at the last index int prevVal = arr[n - 1]; for (int idx = n - 2; idx >= 0; idx--) { totalSplits += (arr[idx] - 1) / prevVal; int numGroups = ((arr[idx] - 1) / prevVal + 1); prevVal = arr[idx] / numGroups; } return totalSplits; } // Driver code public static void main(String[] args) { int arr[] = { 3, 2, 4 }; int N = arr.length; int minSplit = minimumSplits(arr, N); System.out.print(minSplit); }} |
Python3
# Python code to implement the approach# Function to find the minimum# number of splitdef minimumSplits(arr): totalSplits = 0 # Get the value at the last index prevVal = arr[len(arr) - 1] for idx in range(len(arr) - 2,-1,-1): totalSplits += (arr[idx] - 1) // prevVal numGroups = ((arr[idx] - 1) // prevVal + 1) prevVal = arr[idx] // numGroups return totalSplits# Driver Codearr = [ 3, 2, 4 ]# Function callminSplit = minimumSplits(arr)print(minSplit)# This code is contributed by shinjanpatra |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;public class GFG{ // Function to count the minimum // number of splits public static int minimumSplits(int[] arr, int n) { int totalSplits = 0; // Get the value at the last index int prevVal = arr[n - 1]; for (int idx = n - 2; idx >= 0; idx--) { totalSplits += (arr[idx] - 1) / prevVal; int numGroups = ((arr[idx] - 1) / prevVal + 1); prevVal = arr[idx] / numGroups; } return totalSplits; } // Driver Code public static void Main(string[] args) { int[] arr = { 3, 2, 4 }; int N = arr.Length; // function call int minSplit = minimumSplits(arr, N); Console.Write(minSplit); }}// This code is contributed by phasing17 |
Javascript
<script> // JavaScript code to implement the approach // Function to find the minimum // number of split const minimumSplits = (arr) => { let totalSplits = 0; // Get the value at the last index let prevVal = arr[arr.length - 1]; for (let idx = arr.length - 2; idx >= 0; idx--) { totalSplits += parseInt((arr[idx] - 1) / prevVal); let numGroups = parseInt((arr[idx] - 1) / prevVal + 1); prevVal = parseInt(arr[idx] / numGroups); } return totalSplits; } // Driver Code let arr = [3, 2, 4]; // Function call let minSplit = minimumSplits(arr); document.write(minSplit);// This code is contributed by rakeshsahni</script> |
1
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
