Given a positive integer N and K, the task is to divide N into K parts such that the first part has a value X, the second part is 2X, and so on for some value of X. If such division is not possible then print -1.
Examples:
Input: N = 10, K = 4
Output: 1 2 3 4
Explanation:
If we take 1 as first number second number will be 2 third number will be 3 times first which is 3 and the last number will be 4 times third number so last number is 4. We can note that sum=1+2+3+4=10 which is the required sum.Input N = 10, K = 3
Output: -1
Explanation:
Distributing N in 3 parts with given constraint is not possible.
Approach: To solve the problem mentioned above let’s to understand it’s mathematical implementation. Let the division be X1, X2, X3 up to XK where the second integer is X1 * 2, third one is X1 * 3 and the Kth one is X1 * K.
We know that,
=>
=>
=>
=>, where ( 1 + 2 + 3 + … + K) =
=>
, where ( 1 + 2 + 3 + … + K) = 
So to solve the problem we have to follow the steps given below:
- Calculate the value of K * (K + 1) and divide 2 * N by K * (K + 1) in order to get value of X1.
- If X1 is not an integer in the above step then print -1 as there is no such division is possible.
- To get the value of X2 we will multiply X1 by 2. Similarly, to get XK multiply X1 with K.
- After finding all the values print them.
Below is the implementation of above approach:
C++
// C++ program for the above approach#include <iostream>using namespace std;typedef long long int ll;// Function to find the divisionvoid solve(int n, int k){ int x1, d; // Calculating value of x1 d = k * (k + 1); // Print -1 if division // is not possible if ((2 * n) % d != 0) { cout << "-1"; return; } x1 = 2 * n / d; // Get the first number ie x1 // then successively multiply // it by x1 k times by index number // to get the required answer for (int i = 1; i <= k; i++) { cout << x1 * i << " "; } cout << endl;}// Driver Codeint main(){ // Given N and K int n = 10, k = 4; // Function Call solve(n, k);} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find the divisionstatic void solve(int n, int k){ int x1, d; // Calculating value of x1 d = k * (k + 1); // Print -1 if division // is not possible if ((2 * n) % d != 0) { System.out.print("-1"); return; } x1 = 2 * n / d; // Get the first number ie x1 // then successively multiply // it by x1 k times by index number // to get the required answer for (int i = 1; i <= k; i++) { System.out.print(x1 * i+ " "); } System.out.println();}// Driver Codepublic static void main(String[] args){ // Given N and K int n = 10, k = 4; // Function Call solve(n, k);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approach# Function to find the divisiondef solve(n, k): # Calculating value of x1 d = k * (k + 1); # Print -1 if division # is not possible if ((2 * n) % d != 0): print("-1"); return; x1 = 2 * n // d; # Get the first number ie x1 # then successively multiply # it by x1 k times by index number # to get the required answer for i in range(1, k + 1): print(x1 * i, end = " ");# Driver Code# Given N and Kn = 10; k = 4;# Function Callsolve(n, k);# This code is contributed by Code_Mech |
C#
// Java program for the above approachimport java.util.*;class GFG{// Function to find the divisionstatic void solve(int n, int k){ int x1, d; // Calculating value of x1 d = k * (k + 1); // Print -1 if division // is not possible if ((2 * n) % d != 0) { System.out.print("-1"); return; } x1 = 2 * n / d; // Get the first number ie x1 // then successively multiply // it by x1 k times by index number // to get the required answer for (int i = 1; i <= k; i++) { System.out.print(x1 * i+ " "); } System.out.println();}// Driver Codepublic static void main(String[] args){ // Given N and K int n = 10, k = 4; // Function Call solve(n, k);}}// This code is contributed by 29AjayKumar |
1 2 3 4
Time Complexity: O(K)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
