Terms Of AP

Easy
0/40
Average time to solve is 10m
profile
Contributed by
92 upvotes
Asked in companies
Hewlett Packard EnterpriseNucleus SoftwareQuest Global Pvt. Services Ltd

Problem statement

Ayush is given a number ‘X’. He has been told that he has to find the first ‘X’ terms of the series 3 * ‘N’ + 2, which are not multiples of 4. Help Ayush to find it as he has not been able to answer.

Example: Given an ‘X’ = 4. The output array/list which must be passed to Ayush will be [ 5, 11, 14, 17 ].

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain one integer, ‘X’ that denotes the number of terms he has to answer.
Output Format: 
For each test case, return a vector with the first ‘X’ integer of the series 3 * ‘N’ + 2, which is not multiple of 4.

Output for every test case will be printed in a separate line.
Note: 
You don’t need to print anything; It has already been taken care of.
Constraints: 
1 <= T <= 10^2
1 <= X <= 10^5

Time Limit: 1 sec
Sample Input 1:
2
2
5
Sample Output 1:
5 11
5 11 14 17 23
Explanation For Sample Input 1:
In the first test case, the first number is 5, while the second number cannot be 8 as it is divisible by 4, and so, the next number is directly 11 as it is not divisible by 4.

In the second test case, the first two numbers are 5 and 11. While following three numbers are 14, 17 and 23 for ‘N’ = 4, 5 and 7 respectively. 20 is divisible by 4, and thus, 20 cannot be included in the list.
Sample Input 2:
2
7
8
Sample Output 2:
5 11 14 17 23 26 29
5 11 14 17 23 26 29 35
Explanation For Sample Input 2:
In the first test case, the first five numbers are 5, 11, 14, 17 and 23. While the following two numbers are 26 and 29 for N = 8 and 9 respectively.

In the second test case, the seven numbers are explained in the above test case and for N = 10, we get the number 32, which is divisible by 4 and thus, we reject it. For N = 11, the number is 35 and is not divisible by 4.
Hint

Can you think of checking all the numbers one by one?

Approaches (1)
Brute Force

The basic idea of this approach is to iterate through all the elements obtained in series 3 * ‘N’ + 2. We will see if the number is divisible by 4 or not. If it is acceptable, then we will store it in our final answer array/list. We will run the process until we don’t get the first ‘X’ number of elements.

 

Here is the algorithm:

 

  1. Declare a temporary array/list variable ‘ANS’ in which we store our answer.
  2. Declare a temporary variable ‘GOT’ that will store the total number of elements we obtained until now, which are acceptable.
  3. Declare a temporary variable ‘CURRENT’ that will store the current number of series 3 * ‘N’ + 2 and initialize with the first number of series 5.
  4. Run a loop while ‘GOT’ is not equal to ‘X’:
    • If ‘CURRENT’ is not divisible by 4, we will append the value at the end of ‘ANS’ and increment the value of ‘GOT’ by 1.
    • Increment the value of ‘CURRENT’ by three as the next value of the series.
  5. Finally, return ‘ANS’.
Time Complexity

O(N), where N is the number of elements we have to find in the series.
 

Because we will iterate the loop until the number of elements in the array/list is not equal to ‘X’. The number of elements rejected is approximately one-third of the elements accepted. Thus, the time complexity is O(N).

 

Space Complexity

O(N), where N is the number of elements we have to find in the series.

 

Because we are using an array/list of size ‘N’to find our answer. Hence the space complexity is O(N).

Code Solution
(100% EXP penalty)
Terms Of AP
Full screen
Console