Given a number N and an integer S, the task is to create an array of N integers such that sum of all elements equals to S and print an element K where 0 ? K ? S, such that there exists no subarray with sum equals to K or (S – K).
If no such array is possible then print “-1”.
Note: There can be more than one value for K. You can print any one of them.
Examples:
Input: N = 1, S = 4
Output: {4}
K = 2
Explanation:
There exists an array {4} whose sum is 4.
From all possible value of K i.e., 0 ? K ? 4, K = 1, 2, and 3 satisfy the given conditions.
For K = 2, there is no subarray whose sum is 2 or S – K i.e., 4 – 2 = 2.
Input: N = 3, S = 8
Output: {2, 2, 4}
K = 1
Explanation:
There exists an array {2, 2, 4} and there exists K as 1 such that there is no subarray whose sum is 1 and S – K i.e., 8 – 1 = 7.
Approach: To solve the problem mentioned above we have to observe that:
- If 2 * N > S then there is no array possible.
For Example:
For N = 3 and S = 4, then the possible arrays are {1, 2, 1}, {1, 1, 2}, {2, 1, 1}.
The possible values for K are 0, 1, 2, 3 (0 < = k < = S).
But there is no value for K which satisfy the condition.
So the solution to this is not possible.
- An array is only possible if 2 * N <= S and the array can be created using elements (N-1) times 2 and the last element as S – (2 * (N – 1)) and K will always be 1.
Below is the implementation of the above approach:
C++
// C++ for the above approach#include<bits/stdc++.h>using namespace std; // Function to create an array with// N elements with sum as S such that// the given conditions satisfyvoid createArray(int n, int s){ // Check if the solution exists if (2 * n <= s) { // Print the array as // print (n-1) elements // of array as 2 for(int i = 0; i < n - 1; i++) { cout << "2" << " "; s -= 2; } // Print the last element // of the array cout << s << endl; // Print the value of k cout << "1" << endl; } else // If solution doesnot exists cout << "-1" << endl;}// Driver Codeint main(){ // Given N and sum S int N = 1; int S = 4; // Function call createArray(N, S);}// This code is contributed by Ritik Bansal |
Java
// Java for the above approachclass GFG{ // Function to create an array with// N elements with sum as S such that// the given conditions satisfystatic void createArray(int n, int s){ // Check if the solution exists if (2 * n <= s) { // Print the array as // print (n-1) elements // of array as 2 for (int i = 0; i < n - 1; i++) { System.out.print(2 + " "); s -= 2; } // Print the last element // of the array System.out.println(s); // Print the value of k System.out.println(1); } else // If solution doesnot exists System.out.print("-1");}// Driver Codepublic static void main(String[] args) { // Given N and sum S int N = 1; int S = 4; // Function call createArray(N, S);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 for the above approach# Function to create an array with# N elements with sum as S such that# the given conditions satisfydef createArray(n, s): # Check if the solution exists if (2 * n<= s): # Print the array as # print (n-1) elements # of array as 2 for i in range(n-1): print(2, end =" ") s-= 2 # Print the last element # of the array print(s) # Print the value of k print(1) else: # If solution doesnot exists print('-1')# Driver Code # Given N and sum S N = 1S = 4# Function callcreateArray(N, S) |
C#
// C# program for the above approachusing System;class GFG{ // Function to create an array with// N elements with sum as S such that// the given conditions satisfystatic void createArray(int n, int s){ // Check if the solution exists if (2 * n <= s) { // Print the array as // print (n-1) elements // of array as 2 for(int i = 0; i < n - 1; i++) { Console.Write(2 + " "); s -= 2; } // Print the last element // of the array Console.WriteLine(s); // Print the value of k Console.WriteLine(1); } else // If solution doesnot exists Console.Write("-1");}// Driver Codepublic static void Main() { // Given N and sum S int N = 1; int S = 4; // Function call createArray(N, S);}}// This code is contributed by Code_Mech |
Javascript
<script>// JavaScript program to implement// the above approach// Function to create an array with// N elements with sum as S such that// the given conditions satisfyfunction createArray(n, s){ // Check if the solution exists if (2 * n <= s) { // Print the array as // print (n-1) elements // of array as 2 for (let i = 0; i < n - 1; i++) { document.write(2 + " "); s -= 2; } // Print the last element // of the array document.write(s + "<br/>"); // Print the value of k document.write(1); } else // If solution doesnot exists document.write("-1");}// Driver code // Given N and sum S let N = 1; let S = 4; // Function call createArray(N, S);// This code is contributed by sanjoy_62.</script> |
4 1
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
