Given two integers N and K, the task is to generate a series of N terms in which every term is sum of the previous K terms.
Note: The first term of the series is 1. if there are not enough previous terms, then other terms are supposed to be 0.
Examples:
Input: N = 8, K = 3
Output: 1 1 2 4 7 13 24 44
Explanation:
Series is generated as follows:
a[0] = 1
a[1] = 1 + 0 + 0 = 1
a[2] = 1 + 1 + 0 = 2
a[3] = 2 + 1 + 1 = 4
a[4] = 4 + 2 + 1 = 7
a[5] = 7 + 4 + 2 = 13
a[6] = 13 + 7 + 4 = 24
a[7] = 24 + 13 + 7 = 44
Input: N = 10, K = 4
Output: 1 1 2 4 8 15 29 56 108 208
Naive Approach: The idea is to run two loops to generate N terms of series. Below is the illustration of the steps:
- Traverse the first loop from 0 to N – 1, to generate every term of the series.
- Run a loop from max(0, i – K) to i to compute the sum of the previous K terms.
- Update the sum to the current index of series as the current term.
Below is the implementation of the above approach:
C++
// C++ implementation to find the// series in which every term is// sum of previous K terms#include <iostream>using namespace std;// Function to generate the// series in the form of arrayvoid sumOfPrevK(int N, int K){ int arr[N]; arr[0] = 1; // Pick a starting point for (int i = 1; i < N; i++) { int j = i - 1, count = 0, sum = 0; // Find the sum of all // elements till count < K while (j >= 0 && count < K) { sum += arr[j]; j--; count++; } // Find the value of // sum at i position arr[i] = sum; } for (int i = 0; i < N; i++) { cout << arr[i] << " "; }}// Driver Codeint main(){ int N = 10, K = 4; sumOfPrevK(N, K); return 0;} |
Java
// Java implementation to find the// series in which every term is// sum of previous K termsclass Sum { // Function to generate the // series in the form of array void sumOfPrevK(int N, int K) { int arr[] = new int[N]; arr[0] = 1; // Pick a starting point for (int i = 1; i < N; i++) { int j = i - 1, count = 0, sum = 0; // Find the sum of all // elements till count < K while (j >= 0 && count < K) { sum += arr[j]; j--; count++; } // Find the value of // sum at i position arr[i] = sum; } for (int i = 0; i < N; i++) { System.out.print(arr[i] + " "); } } // Driver Code public static void main(String args[]) { Sum s = new Sum(); int N = 10, K = 4; s.sumOfPrevK(N, K); }} |
Python3
# Python3 implementation to find the # series in which every term is # sum of previous K terms # Function to generate the # series in the form of array def sumOfPrevK(N, K): arr = [0 for i in range(N)] arr[0] = 1 # Pick a starting point for i in range(1,N): j = i - 1 count = 0 sum = 0 # Find the sum of all # elements till count < K while (j >= 0 and count < K): sum = sum + arr[j] j = j - 1 count = count + 1 # Find the value of # sum at i position arr[i] = sum for i in range(0, N): print(arr[i])# Driver Code N = 10K = 4sumOfPrevK(N, K)# This code is contributed by Sanjit_Prasad |
C#
// C# implementation to find the// series in which every term is// sum of previous K termsusing System;class Sum { // Function to generate the // series in the form of array void sumOfPrevK(int N, int K) { int []arr = new int[N]; arr[0] = 1; // Pick a starting point for (int i = 1; i < N; i++) { int j = i - 1, count = 0, sum = 0; // Find the sum of all // elements till count < K while (j >= 0 && count < K) { sum += arr[j]; j--; count++; } // Find the value of // sum at i position arr[i] = sum; } for (int i = 0; i < N; i++) { Console.Write(arr[i] + " "); } } // Driver Code public static void Main(String []args) { Sum s = new Sum(); int N = 10, K = 4; s.sumOfPrevK(N, K); }}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript implementation to find the// series in which every term is// sum of previous K terms// Function to generate the// series in the form of arrayfunction sumOfPrevK(N, K){ let arr = new Array(N); arr[0] = 1; // Pick a starting point for (let i = 1; i < N; i++) { let j = i - 1, count = 0, sum = 0; // Find the sum of all // elements till count < K while (j >= 0 && count < K) { sum += arr[j]; j--; count++; } // Find the value of // sum at i position arr[i] = sum; } for (let i = 0; i < N; i++) { document.write(arr[i] + " "); }}// Driver Codelet N = 10, K = 4;sumOfPrevK(N, K);// This code is contributed by _saurabh_jaiswal</script> |
Output:
1 1 2 4 8 15 29 56 108 208
Performance analysis:
- Time Complexity: O(N * K)
- Space Complexity: O(N)
Improved Approach: The idea is to store the current sum in a variable and subtract the last Kth term in every step and add the last term into the pre-sum to compute every term of the series.
Below is the implementation of the above approach:
C++
#include <iostream>#include <vector>using namespace std;void sumOfPrevK(int N, int K){ vector<int> arr(N); // initialize the 0th index with 1 arr[0] = 1; // initialize sliding window and sum // the sum stores the sum of the previous window int start = 0, end = 1, sum = 1; while (end < N) { // if size of the sliding window exceeds K if (end - start > K) { // decrease the window size and update the sum sum -= arr[start]; ++start; } // update the current element by sum of the previous // K elements arr[end] = sum; // Update the sum by adding the current element sum += arr[end]; // increase the window size ++end; } for (int i = 0; i < N; ++i) { cout << arr[i] << " "; } cout << endl;}int main(){ int N = 10, K = 4; sumOfPrevK(N, K); return 0;} |
Java
// Java code to implement the approachimport java.util.*;class GFG { static void sumOfPrevK(int N, int K) { ArrayList<Integer> arr = new ArrayList<Integer>(); for (int i = 0; i < N; i++) arr.add(0); // initialize the 0th index with 1 arr.set(0, 1); // initialize sliding window and sum // the sum stores the sum of the previous window int start = 0, end = 1, sum = 1; while (end < N) { // if size of the sliding window exceeds K if (end - start > K) { // decrease the window size and update the // sum sum -= arr.get(start); ++start; } // update the current element by sum of the // previous K elements arr.set(end, sum); // Update the sum by adding the current element sum += arr.get(end); // increase the window size ++end; } for (int i = 0; i < N; ++i) { System.out.print(arr.get(i) + " "); } System.out.print("\n"); } public static void main(String[] args) { int N = 10, K = 4; sumOfPrevK(N, K); }}// This code is contributed by phasing17 |
Python3
# Python3 code to implement the approachdef sumsOfPrevK(N, K): arr = [0 for _ in range(N)] # initialize the 0th index with 1 arr[0] = 1 # initialize sliding window and sums # the sums stores the sums of the previous window start = 0 end = 1 sums = 1 while (end < N): # if size of the sliding window exceeds K if (end - start > K): # decrease the window size and update the sums sums -= arr[start] start += 1 # update the current element by sums of the previous # K elements arr[end] = sums # Update the sums by adding the current element sums += arr[end] # increase the window size end += 1 print(*arr)# Driver CodeN = 10K = 4sumsOfPrevK(N, K)# This code is contributed by phasing17 |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;class GFG{ static void sumOfPrevK(int N, int K) { List<int> arr = new List<int>() ; for (int i = 0; i < N; i++) arr.Add(0); // initialize the 0th index with 1 arr[0] = 1; // initialize sliding window and sum // the sum stores the sum of the previous window int start = 0, end = 1, sum = 1; while (end < N) { // if size of the sliding window exceeds K if (end - start > K) { // decrease the window size and update the sum sum -= arr[start]; ++start; } // update the current element by sum of the previous // K elements arr[end] = sum; // Update the sum by adding the current element sum += arr[end]; // increase the window size ++end; } for (int i = 0; i < N; ++i) { Console.Write(arr[i] + " "); } Console.Write("\n"); } public static void Main(string[] args) { int N = 10, K = 4; sumOfPrevK(N, K); }}// This code is contributed by phasing17 |
Javascript
// JavaScript code to implement the approachfunction sumOfPrevK(N, K){ let arr = new Array(N); // initialize the 0th index with 1 arr[0] = 1; // initialize sliding window and sum // the sum stores the sum of the previous window let start = 0, end = 1, sum = 1; while (end < N) { // if size of the sliding window exceeds K if (end - start > K) { // decrease the window size and update the sum sum -= arr[start]; ++start; } // update the current element by sum of the previous // K elements arr[end] = sum; // Update the sum by adding the current element sum += arr[end]; // increase the window size ++end; } console.log(arr.join(" ")) }// Driver Codelet N = 10, K = 4;sumOfPrevK(N, K);// This code is contributed by phasing17 |
Complexity analysis:
- Time Complexity: O(N)
- Space Complexity: O(N)
Another Approach: Sliding Window
The idea is to use a fixed-size sliding window of size K to get the sum of previous K elements.
- Initialize the answer array with arr[0] = 1 and a variable sum = 1, representing the sum of the last K elements. Initially, the previous sum = 1. (If there are less than K elements in the last window, then the sum will store the sum of all the elements in the window)
- The sliding window is initialized by making start = 0 and end = 1.
- If the window size exceeds K, then decrement arr[start] from sum and increment start to update the window size and sum.
- Make arr[end] = sum, which will be the sum of the previous K elements, and increment sum by arr[end] for the next iteration. Increment end by 1.
Output
1 1 2 4 8 15 29 56 108 208
Complexity analysis:
- Time Complexity: O(N)
- Auxiliary Space: O(N)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
