Minimize moves to sort Array in non decreasing order by breaking elements in two parts

0 0 4 minutes read

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 split
int 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 Code
int 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 split
def 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 Code
arr = [ 3, 2, 4 ]
 
# Function call
minSplit = minimumSplits(arr)
print(minSplit)
 
# This code is contributed by shinjanpatra

C#

// C# code to implement the approach
using 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

Time Complexity: O(N)
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!