Generate an N-length array having sum of each subarray divisible by K
Given two positive integers N and K, the task is to generate an array consisting of N distinct integers such that the sum of elements of each subarray of the constructed array is divisible by K.
Examples:
Input: N = 3, K = 3
Output: 3 6 9
Explanation:
The subarrays of the resultant array are {3}, {6}, {3, 6}, {9}, {6, 9}, {3, 6, 9}. Sum of all these subarrays are divisible by K.Input: N = 5, K = 1
Output: 1 2 3 4 5
Approach: Follow the steps below to solve the problem:
- Since the sum of elements of each subarray needs to be divisible by K, the most optimal approach would be to construct an array with each element being a multiple of K.
- Therefore, iterate a loop from i = 1 to i = N and for each value of i, print K * i.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to construct an array // with sum of each subarray // divisible by K void construct_Array( int N, int K) { // Traverse a loop from 1 to N for ( int i = 1; i <= N; i++) { // Print i-th multiple of K cout << K * i << " " ; } } // Driver Code int main() { int N = 3, K = 3; construct_Array(N, K); return 0; } |
Java
// Java program to implement // the above approach import java.io.*; import java.util.*; class GFG { // Function to construct an array // with sum of each subarray // divisible by K static void construct_Array( int N, int K) { // Traverse a loop from 1 to N for ( int i = 1 ; i <= N; i++) { // Print i-th multiple of K System.out.print(K * i + " " ); } } // Driver Code public static void main(String[] args) { int N = 3 , K = 3 ; construct_Array(N, K); } } // This code is contributed by code hunt. |
Python3
# Python program for the above approach # Function to construct an array # with sum of each subarray # divisible by K def construct_Array(N, K) : # Traverse a loop from 1 to N for i in range ( 1 , N + 1 ): # Pri-th multiple of K print (K * i, end = " " ) # Driver Code N = 3 K = 3 construct_Array(N, K) # This code is contributed by splevel62. |
C#
// C# program to implement // the above approach using System; public class GFG { // Function to construct an array // with sum of each subarray // divisible by K static void construct_Array( int N, int K) { // Traverse a loop from 1 to N for ( int i = 1; i <= N; i++) { // Print i-th multiple of K Console.Write(K * i + " " ); } } // Driver Code public static void Main(String[] args) { int N = 3, K = 3; construct_Array(N, K); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program for the above approach // Function to construct an array // with sum of each subarray // divisible by K function construct_Array(N, K) { // Traverse a loop from 1 to N for (let i = 1; i <= N; i++) { // Print i-th multiple of K document.write( K * i + " " ); } } // Driver Code let N = 3, K = 3; construct_Array(N, K); // This code is contributed by todaysgaurav </script> |
Output:
3 6 9
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us