Given three integers N, K and S, the task is to choose an array of size N such that there exists exactly K sub-arrays with sum S.
Note: There can be many solution arrays to this problem.
Examples:
Input: N = 4, K = 2, S = 3
Output: 1 2 3 4
Explanation:
One of the possible array is [ 1, 2, 3, 4 ]
There exist exactly two subarrays with sum 3
Subarrays with Sum(3) = [ [ 1, 2 ], [ 3 ] ]
Input: N = 5, K = 3, S = 50
Output: 25 25 25 10 40
Explanation:
One of the possible array is [ 25, 25, 25, 10, 40 ]
There exist exactly three subarrays with sum 50
Subarrays with Sum(50) = [ [ 25, 25 ], [ 25, 25 ], [ 10, 40 ] ]
Approach:
One of the Solution Array for this problem contains S element K times and S+1 element (N-K) times, to form K Sub-arrays of exactly one element with S as sum. If we combine any two or more elements of the array then it will give sum greater than S.
Below is the implementation of the above approach:
C++
// C++ program to find array // with K subarrays with sum S #include<bits/stdc++.h> using namespace std; // Function to find array // with K subarrays with sum S void SubarraysWithSumS(int n, int k, int s) { for(int i=0;i<k;i++) cout << s << " "; for(int i=k;i<n;i++) cout << s+1 << " "; } // Driver Code int main() { int n = 4, k = 2, s = 3; // Function call SubarraysWithSumS(n, k, s); return 0; } |
Java
// Java program to find array // with K subarrays with sum S class GFG { // Function to find array // with K subarrays with sum S static void SubarraysWithSumS(int n, int k, int s) { for(int i = 0; i < k; i++) System.out.print(s + " "); for(int i = k; i < n; i++) System.out.print(s + 1 + " "); } // Driver Code public static void main(String[] args) { int n = 4, k = 2, s = 3; // Function call SubarraysWithSumS(n, k, s); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program to find array # with K subarrays with sum S # Function to find array # with K subarrays with sum S def SubarraysWithSumS(n, k, s): for i in range(k): print(s, end=" ") for i in range(k, n): print(s + 1, end = " ") # Driver Code n = 4k = 2s = 3 # Function call SubarraysWithSumS(n, k, s) # This code is contributed by mohit kumar 29 |
C#
// C# program to find array // with K subarrays with sum S using System; class GFG { // Function to find array // with K subarrays with sum S static void SubarraysWithSumS(int n, int k, int s) { for(int i = 0; i < k; i++) Console.Write(s + " "); for(int i = k; i < n; i++) Console.Write(s + 1 + " "); } // Driver Code public static void Main(String[] args) { int n = 4, k = 2, s = 3; // Function call SubarraysWithSumS(n, k, s); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // Javascript program to find array // with K subarrays with sum S // Function to find array // with K subarrays with sum S function SubarraysWithSumS(n,k,s) { for(let i = 0; i < k; i++) document.write(s + " "); for(let i = k; i < n; i++) document.write(s + 1 + " "); } // Driver Code let n = 4, k = 2, s = 3; // Function call SubarraysWithSumS(n, k, s); // This code is contributed by unknown2108 </script> |
3 3 4 4
Time Complexity: O(n)
Auxiliary Space: O(1)
Related Topic: Subarrays, Subsequences, and Subsets in Array
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
