Find an array of size N having exactly K subarrays with sum S

0 0 3 minutes read

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 = 4
k = 2
s = 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> 

Output:

3 3 4 4

Time Complexity: O(n)

Auxiliary Space: O(1)

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 zambiatek!