[Solved] Print Series Contest Problem

Print Series: You have given two positive integers N and K. Your task is to print a series of numbers i.e subtract K from N until it becomes 0 or negative then add K until it becomes N. You need to do this task without using any loop.

For Example:

For  N = 5 , K = 2 
Series = [ 5, 3, 1, -1, 1, 3, 5]

Print Series Contest Problem

Input Format :

The first line of input contains a single integer T, representing the number of test cases or queries to be run 

The first line of each test contains two space-separated integers N and K. 

Output Format :

For each test case, print a single line containing the required series.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 100   
1 <= N <= 3000 
1 <= K <= N 

Time Limit: 1sec

Sample Input 1 :

2 
3 2
5 4

Sample Output 1 :

3 1 -1 1 3
5 1 -3 1 5

Explanation For Sample 1:

For the 1st test case:
The numbers in the sequence are 3, 3 - 2, 3 - 2 - 2, 3 - 2 - 2 + 2, 3 - 2 - 2 + 2 + 2, which is the same as 3, 1, -1, 1, 3. 

For the 2nd test case:
The numbers in the sequence are 5, 5 - 4, 5 - 4 - 4, 5 - 4 - 4 + 4, 5 - 4 - 4 + 4 + 4, which is the same as 5, 1, -3, 1, 5. 

Sample Input 2 :

1
4 2

Sample Output 2 :

4 2 0 2 4

Solution

Recursion:

The idea here is to use recursion,we can print current N two times in the current recursion stack. One for decreasing order and one for increasing order. 

Steps : 

• Declare an empty array to store our series, say answer.
• Define and call function series(answer, N, K), where N, and K is the given number.
• At last return answer.

void series(answer, N, K):

• Add N to answer.
• Base condition, if N equals to 0 or negative then return.
• Recur for series(answer, N – K, K).
• Add N to answer.

Time Complexity:

O(N), where N is the given number.

In the worst case when K = 1 we need to recur for O(N) times. Hence the overall complexity will be O(N). 

Space Complexity:

O(N), where N is the given number.

In the worst case, when K = 1 we need O(N) recursion calls. Hence the overall complexity will be O(N).

/*
	Time Complexity  : O(N)
	Space Complexity : O(N)

	Where N is the given number.
*/

import java.util.List;
import java.util.ArrayList;

public class Solution {
    public static List<Integer> printSeries(int n, int k) {

        // Declare an empty array to store our series
        List<Integer> answer = new ArrayList<>();

        // Call the series function
        series(n, k, answer);

        // Return the answer
        return answer;
    }

    private static void series(int n, int k, List<Integer> answer) {
    	
        // Add n to answer
        answer.add(n);

        // If n<=0 then break the recursion
        if (n <= 0) {
            return;
        }

        // Recur for series(answer, n, n-k).
        series(n - k, k, answer);

        // Add n to answer.
        answer.add(n);
    }
}

/*
    Time Complexity  : O(N)
    Space Complexity : O(N)

    Where N is the given number.
*/

void series(int n, int k, vector<int> &answer)
{
    
    // Add n to answer
    answer.push_back(n);

    // If n<=0 then break the recursion
    if (n <= 0)
    {
        return;
    }

    // Recur for series(answer, n, n-k).
    series(n - k, k, answer);

    // Add n to answer.
    answer.push_back(n);
}

vector<int> printSeries(int n, int k)
{
    
    // Declare an empty array to store our series
    vector<int> answer;

    // Call the series function
    series(n, k, answer);

    // Return the answer
    return answer;
}

'''
    Time Complexity  : O(N)
    Space Complexity : O(N)

    Where N is the given number.
'''

def series(n, k, answer):
    
    # Add n to answer
    answer.append(n)

    # If n<=0 then break the recursion
    if (n <= 0):
        return

    # Recur for series(answer, n, n-k).
    series(n - k, k, answer)

    # Add n to answer.
    answer.append(n)


def printSeries(n, k):
    
    # Declare an empty array to store our series
    answer = []

    # Call the series function
    series(n, k, answer)

    # Return the answer
    return answer

Happy Learning – If you require any further information, feel free to contact me.