Generate array with minimum sum which can be deleted in P steps
Given two numbers N and P. The task is to generate an array of all positive elements, and in one operation you can choose a minimum number in the array and subtract it from all array elements. If the array element becomes 0 then you will remove it.
You have to print the minimum possible sum of the array and one possible array such that after applying exactly P steps the array will vanish.
Examples:
Input : N = 4, P = 2
Output :
The Minimum Possible Sum is: 5
The Array Elements are: 1 2 1 1
Explanation:
The array can be [1, 2, 1, 1] after 1st step it becomes [0, 1, 0, 0] and it becomes [1] and after step 2 it will be vanished.Thus the sum is 5 and it is minimum possible value.
Input : N = 3 , P = 1
Output :
The Minimum Possible Sum is: 3
The Array Elements are: 1 1 1
Approach: The problem can be solved by following a greedy approach. First, we will place first P natural numbers, and for the rest (N – P) positions we will fill it with 1 because we have to minimize the sum.
So the sum will be P*(P+1)/2 + (N – P).
Below is the implementation of the above approach:
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; // Function to find the required array void findArray( int N, int P) { // calculating minimum possible sum int ans = (P * (P + 1)) / 2 + (N - P); // Array int arr[N + 1]; // place first P natural elements for ( int i = 1; i <= P; i++) arr[i] = i; // Fill rest of the elements with 1 for ( int i = P + 1; i <= N; i++) arr[i] = 1; cout << "The Minimum Possible Sum is: " << ans << "\n" ; cout << "The Array Elements are: \n" ; for ( int i = 1; i <= N; i++) cout << arr[i] << ' ' ; } // Driver Code int main() { int N = 5, P = 3; findArray(N, P); return 0; } |
Java
// Java implementation of the approach class GFG { // Function to find the required array static void findArray( int N, int P) { // calculating minimum possible sum int ans = (P * (P + 1 )) / 2 + (N - P); // Array int arr[] = new int [N + 1 ]; // place first P natural elements for ( int i = 1 ; i <= P; i++) { arr[i] = i; } // Fill rest of the elements with 1 for ( int i = P + 1 ; i <= N; i++) { arr[i] = 1 ; } System.out.print( "The Minimum Possible Sum is: " + ans + "\n" ); System.out.print( "The Array Elements are: \n" ); for ( int i = 1 ; i <= N; i++) { System.out.print(arr[i] + " " ); } } // Driver Code public static void main(String[] args) { int N = 5 , P = 3 ; findArray(N, P); } } // This code contributed by Rajput-Ji |
Python3
# Python3 implementation of above approach # Function to find the required array def findArray(N, P): # calculating minimum possible sum ans = (P * (P + 1 )) / / 2 + (N - P); # Array arr = [ 0 ] * (N + 1 ); # place first P natural elements for i in range ( 1 , P + 1 ): arr[i] = i; # Fill rest of the elements with 1 for i in range (P + 1 , N + 1 ): arr[i] = 1 ; print ( "The Minimum Possible Sum is: " , ans); print ( "The Array Elements are: " ); for i in range ( 1 , N + 1 ): print (arr[i], end = " " ); # Driver Code N = 5 ; P = 3 ; findArray(N, P); # This code is contributed by mits |
C#
// C# implementation of the approach using System; class GFG { // Function to find the required array static void findArray( int N, int P) { // calculating minimum possible sum int ans = (P * (P + 1)) / 2 + (N - P); // Array int []arr = new int [N + 1]; // place first P natural elements for ( int i = 1; i <= P; i++) { arr[i] = i; } // Fill rest of the elements with 1 for ( int i = P + 1; i <= N; i++) { arr[i] = 1; } Console.Write( "The Minimum Possible Sum is: " + ans + "\n" ); Console.Write( "The Array Elements are: \n" ); for ( int i = 1; i <= N; i++) { Console.Write(arr[i] + " " ); } } // Driver Code public static void Main() { int N = 5, P = 3; findArray(N, P); } } /* This code contributed by PrinciRaj1992 */ |
PHP
<?php // PHP implementation of above approach // Function to find the required array function findArray( $N , $P ) { // calculating minimum possible sum $ans = ( $P * ( $P + 1)) / 2 + ( $N - $P ); // Array $arr [ $N + 1] = array (); // place first P natural elements for ( $i = 1; $i <= $P ; $i ++) $arr [ $i ] = $i ; // Fill rest of the elements with 1 for ( $i = $P + 1; $i <= $N ; $i ++) $arr [ $i ] = 1; echo "The Minimum Possible Sum is: " , $ans , "\n" ; echo "The Array Elements are: \n" ; for ( $i = 1; $i <= $N ; $i ++) echo $arr [ $i ], ' ' ; } // Driver Code $N = 5; $P = 3; findArray( $N , $P ); // This code is contributed by ajit. ?> |
Javascript
<script> // Javascript implementation of the approach // Function to find the required array function findArray(N, P) { // calculating minimum possible sum let ans = parseInt((P * (P + 1)) / 2, 10) + (N - P); // Array let arr = new Array(N + 1); // place first P natural elements for (let i = 1; i <= P; i++) { arr[i] = i; } // Fill rest of the elements with 1 for (let i = P + 1; i <= N; i++) { arr[i] = 1; } document.write( "The Minimum Possible Sum is: " + ans + "</br>" ); document.write( "The Array Elements are: " + "</br>" ); for (let i = 1; i <= N; i++) { document.write(arr[i] + " " ); } } let N = 5, P = 3; findArray(N, P); </script> |
The Minimum Possible Sum is: 8 The Array Elements are: 1 2 3 1 1
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us