Given two integers N and K, the task is to generate an array arr[] of length K such that:
- arr[0] + arr[1] + … + arr[K – 1] = N.
- arr[i] > 0 for 0 ? i < K.
- arr[i] < arr[i + 1] ? 2 * arr[i] for 0 ? i < K – 1.
If there are multiple answers find any one of them, otherwise, print -1.
Examples:
Input: N = 26, K = 6
Output: 1 2 4 5 6 8
The generated array satisfies all of the given conditions.
Input: N = 8, K = 3
Output: -1
Approach: Let r = n – k * (k + 1) / 2. If r < 0 then answer is -1 already. Otherwise, let’s construct the array arr[], where all arr[i] are floor(r / k) except for rightmost r % k values, they are ceil(r / k).
It is easy to see that the sum of this array is r, it is sorted in non-decreasing order and the difference between the maximum and the minimum element is not greater than 1.
Let’s add 1 to arr[1], 2 to arr[2], and so on (this is what we subtract from n at the beginning).
Then, if r != k – 1 or k = 1 then arr[] is our required array. Otherwise, we got some array of kind 1, 3, ….., arr[k]. For k = 2 or k = 3, there is no answer for this case. Otherwise, we can subtract 1 from arr[2] and add it to arr[k] and this answer will be correct.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to generate and print// the required arrayvoid generateArray(int n, int k){ // Initializing the array vector<int> array(k, 0); // Finding r (from above approach) int remaining = n - int(k * (k + 1) / 2); // If r<0 if (remaining < 0) cout << ("NO"); int right_most = remaining % k; // Finding ceiling and floor values int high = ceil(remaining / (k * 1.0)); int low = floor(remaining / (k * 1.0)); // Fill the array with ceiling values for (int i = k - right_most; i < k; i++) array[i]= high; // Fill the array with floor values for (int i = 0; i < (k - right_most); i++) array[i]= low; // Add 1, 2, 3, ... with corresponding values for (int i = 0; i < k; i++) array[i] += i + 1; if (k - 1 != remaining or k == 1) { for(int u:array) cout << u << " "; } // There is no solution for below cases else if (k == 2 or k == 3) printf("-1\n"); else { // Modify A[1] and A[k-1] to get // the required array array[1] -= 1; array[k - 1] += 1; for(int u:array) cout << u << " "; }}// Driver Codeint main(){ int n = 26, k = 6; generateArray(n, k); return 0;}// This code is contributed // by Mohit Kumar |
Java
// Java implementation of the approachclass GFG{// Function to generate and print// the required arraystatic void generateArray(int n, int k){ // Initializing the array int []array = new int[k]; // Finding r (from above approach) int remaining = n - (k * (k + 1) / 2); // If r < 0 if (remaining < 0) System.out.print("NO"); int right_most = remaining % k; // Finding ceiling and floor values int high = (int) Math.ceil(remaining / (k * 1.0)); int low = (int) Math.floor(remaining / (k * 1.0)); // Fill the array with ceiling values for (int i = k - right_most; i < k; i++) array[i] = high; // Fill the array with floor values for (int i = 0; i < (k - right_most); i++) array[i] = low; // Add 1, 2, 3, ... with corresponding values for (int i = 0; i < k; i++) array[i] += i + 1; if (k - 1 != remaining || k == 1) { for(int u:array) System.out.print(u + " "); } // There is no solution for below cases else if (k == 2 || k == 3) System.out.printf("-1\n"); else { // Modify A[1] and A[k-1] to get // the required array array[1] -= 1; array[k - 1] += 1; for(int u:array) System.out.print(u + " "); }}// Driver Codepublic static void main(String[] args){ int n = 26, k = 6; generateArray(n, k);}}// This code is contributed by PrinciRaj1992 |
Python3
# Python3 implementation of the approachimport sysfrom math import floor, ceil# Function to generate and print # the required arraydef generateArray(n, k): # Initializing the array array = [0] * k # Finding r (from above approach) remaining = n-int(k*(k + 1)/2) # If r<0 if remaining<0: print("NO") sys.exit() right_most = remaining % k # Finding ceiling and floor values high = ceil(remaining / k) low = floor(remaining / k) # Fill the array with ceiling values for i in range(k-right_most, k): array[i]= high # Fill the array with floor values for i in range(k-right_most): array[i]= low # Add 1, 2, 3, ... with corresponding values for i in range(k): array[i]+= i + 1 if k-1 != remaining or k == 1: print(*array) sys.exit() # There is no solution for below cases elif k == 2 or k == 3: print("-1") sys.exit() else: # Modify A[1] and A[k-1] to get # the required array array[1]-= 1 array[k-1]+= 1 print(*array) sys.exit()# Driver Codeif __name__=="__main__": n, k = 26, 6 generateArray(n, k) |
C#
// C# implementation of the approachusing System;class GFG{// Function to generate and print// the required arraystatic void generateArray(int n, int k){ // Initializing the array int []array = new int[k]; // Finding r (from above approach) int remaining = n - (k * (k + 1) / 2); // If r < 0 if (remaining < 0) Console.Write("NO"); int right_most = remaining % k; // Finding ceiling and floor values int high = (int) Math.Ceiling(remaining / (k * 1.0)); int low = (int) Math.Floor(remaining / (k * 1.0)); // Fill the array with ceiling values for (int i = k - right_most; i < k; i++) array[i] = high; // Fill the array with floor values for (int i = 0; i < (k - right_most); i++) array[i] = low; // Add 1, 2, 3, ... with // corresponding values for (int i = 0; i < k; i++) array[i] += i + 1; if (k - 1 != remaining || k == 1) { foreach(int u in array) Console.Write(u + " "); } // There is no solution for below cases else if (k == 2 || k == 3) Console.Write("-1\n"); else { // Modify A[1] and A[k-1] to get // the required array array[1] -= 1; array[k - 1] += 1; foreach(int u in array) Console.Write(u + " "); }}// Driver Codepublic static void Main(String[] args){ int n = 26, k = 6; generateArray(n, k);}}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// javascript implementation of the approach // Function to generate and print // the required array function generateArray(n , k) { // Initializing the array var array = Array(k).fill(0); // Finding r (from above approach) var remaining = n - parseInt(k * (k + 1) / 2); // If r < 0 if (remaining < 0) document.write("NO"); var right_most = remaining % k; // Finding ceiling and floor values var high = parseInt( Math.ceil(remaining / (k * 1.0))); var low = parseInt( Math.floor(remaining / (k * 1.0))); // Fill the array with ceiling values for (i = k - right_most; i < k; i++) array[i] = high; // Fill the array with floor values for (i = 0; i < (k - right_most); i++) array[i] = low; // Add 1, 2, 3, ... with corresponding values for (i = 0; i < k; i++) array[i] += i + 1; if (k - 1 != remaining || k == 1) { for (var u = 0;u< array.length;u++) document.write(array[u] + " "); } // There is no solution for below cases else if (k == 2 || k == 3) document.write("-1"); else { // Modify A[1] and A[k-1] to get // the required array array[1] -= 1; array[k - 1] += 1; for (var f = 0;f< array.length;f++) document.write(array[f] + " "); } } // Driver Code var n = 26, k = 6; generateArray(n, k);// This code is contributed by todaysgaurav </script> |
Output:
1 2 4 5 6 8
Time Complexity: O(K)
Auxiliary Space: O(K)
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!
