Rearrange the given array to minimize the indices with prefix sum at least arr[i]
Given an array arr[] consisting of N positive integers, rearrange the array to minimize the number of indices i such that the prefix sum from index 1 to index i-1 is greater than or equal to the current element arr[i] i.e. arr[1]+arr[2]+…+arr[i-1] >= arr[i].
Examples:
Input: arr[] = [4, 2, 1]
Output:
0
1 2 4
Explanation: If we arrange array as [1, 2, 4], there will be no indices following the criteria.
At index 1, there is no prefix sum.
At index 2, prefix sum = 1 < 2 hence not included in answer.
At index 3, prefix sum= 3 < 4 hence not included in answer.Input: arr[] = [4, 7, 5, 10]
Output:
1
4 5 10 7
Explanation: If we arrange array as [4 5 10 7],
At index 1, there is no prefix sum.
At index 2, prefix sum=4 < 5 hence not included in answer.
At index 3, prefix sum= 9<10 hence not included in answer.
At index 4, prefix sum= 19>=7 hence included in answer.
There can be no other combination which can minimize answer.
Approach: To solve the problem, follow the below idea,
While the initial intuition might suggest sorting the array, it is not an optimal strategy. For example, consider the array [4, 5, 7, 10]. A direct sort could result in two indices following the condition. However, by rearranging the array as [4, 5, 10, 7], the number of indices is minimized to one.
A better approach involves systematically checking each index element that it is possible to add the current element to ans[] vector such that it exceeds its prefix sum. Additionally, any skipped elements between successful additions are included in the final result.
Step-by-step algorithm:
- Sort the array and initialize count = 0.
- Add first element to ans vector.
- Now you just have to iterate over the sorted array.
- If the current element is greater than prefix_sum then you have to just add that element into the answer array otherwise you have to skip that element.
- The ans[] vector contains all the elements not satisfying the condition. Hence the remaining elements are included in count i.e. n-ans.size().
- Push back all the skipped elements (use boolean array for tracking skipped elements).
- Finally print the count and ans array.
Below is the implementation of the above approach:
C++
// c++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find number of // required indices and print the rearranged array int Rearrange_array( int arr[], int N) { // initialising prefix sum long long int prefix = 0; vector< int > ans; vector< bool > checked(N, true ); // sort the array sort(arr, arr + N); ans.push_back(arr[0]); prefix += arr[0]; for ( int i = 1; i < N; i++) { if (arr[i] > prefix) { prefix += arr[i]; ans.push_back(arr[i]); checked[i] = false ; } } // the count of required numbers int count = N - ans.size(); for ( int i = 1; i < N; i++) { if (checked[i]) ans.push_back(arr[i]); } cout << count << endl; for ( auto x : ans) { cout << x << " "; } cout << endl; } // Driver Code int main() { int arr[] = { 4, 7, 5, 10 }; int N = sizeof (arr) / sizeof (arr[0]); Rearrange_array(arr, N); return 0; } |
Java
// java program for the above approach import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class Solution { // Function to find the number of required indices // and print the rearranged array static void rearrangeArray( int [] arr, int N) { // Initializing prefix sum long prefix = 0 ; List<Integer> ans = new ArrayList<>(); boolean [] checked = new boolean [N]; Arrays.fill(checked, true ); // Sort the array Arrays.sort(arr); ans.add(arr[ 0 ]); prefix += arr[ 0 ]; for ( int i = 1 ; i < N; i++) { if (arr[i] > prefix) { prefix += arr[i]; ans.add(arr[i]); checked[i] = false ; } } // The count of required numbers int count = N - ans.size(); for ( int i = 1 ; i < N; i++) { if (checked[i]) { ans.add(arr[i]); } } System.out.println(count); for ( int x : ans) { System.out.print(x + " " ); } System.out.println(); } // Main function public static void main(String[] args) { int [] arr = { 4 , 7 , 5 , 10 }; int N = arr.length; rearrangeArray(arr, N); } } |
Python3
# Python program for the above approach def rearrange_array(arr, N): # Initializing prefix sum prefix = 0 ans = [] checked = [ True ] * N # Sort the array arr.sort() ans.append(arr[ 0 ]) prefix + = arr[ 0 ] for i in range ( 1 , N): if arr[i] > prefix: prefix + = arr[i] ans.append(arr[i]) checked[i] = False # The count of required numbers count = N - len (ans) for i in range ( 1 , N): if checked[i]: ans.append(arr[i]) print (count) for x in ans: print (x, end = " " ) print () # Main function if __name__ = = "__main__" : arr = [ 4 , 7 , 5 , 10 ] N = len (arr) rearrange_array(arr, N) |
C#
//// c# program for the above approach using System; using System.Collections.Generic; public class Solution { // Function to find the number of required indices // and print the rearranged array static void RearrangeArray( int [] arr, int N) { // Initializing prefix sum long prefix = 0; List< int > ans = new List< int >(); bool [] checkedArray = new bool [N]; Array.Fill(checkedArray, true ); // Sort the array Array.Sort(arr); ans.Add(arr[0]); prefix += arr[0]; for ( int i = 1; i < N; i++) { if (arr[i] > prefix) { prefix += arr[i]; ans.Add(arr[i]); checkedArray[i] = false ; } } // The count of required numbers int count = N - ans.Count; for ( int i = 1; i < N; i++) { if (checkedArray[i]) { ans.Add(arr[i]); } } Console.WriteLine(count); foreach ( int x in ans) { Console.Write(x + " " ); } Console.WriteLine(); } // Main function public static void Main( string [] args) { int [] arr = { 4, 7, 5, 10 }; int N = arr.Length; RearrangeArray(arr, N); } } |
Javascript
// Javascript program for the above approach // Function to find the number of required indices // and print the rearranged array function rearrangeArray(arr, N) { // Initializing prefix sum let prefix = 0; let ans = []; let checkedArray = new Array(N).fill( true ); // Sort the array arr.sort((a, b) => a - b); ans.push(arr[0]); prefix += arr[0]; for (let i = 1; i < N; i++) { if (arr[i] > prefix) { prefix += arr[i]; ans.push(arr[i]); checkedArray[i] = false ; } } // The count of required numbers let count = N - ans.length; for (let i = 1; i < N; i++) { if (checkedArray[i]) { ans.push(arr[i]); } } console.log(count); console.log(ans.join( " " )); } // Main function let arr = [4, 7, 5, 10]; let N = arr.length; rearrangeArray(arr, N); |
1 4 5 10 7
Time Complexity: O(N*logN), where N is the size of input array arr[].
Auxiliary Space: O(N)