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 approachÂ
import 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> |
Output
1
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
