Cool sequences

Ninja
0/200
Average time to solve is 70m
profile
Contributed by
1 upvote
Asked in company
Tailnode Technology

Problem statement

Ninja is a big fan of some cool sequences. Let 'A' denote a cool sequence. Ninja says a sequence is cool if the following conditions are satisfied.

Each element of the sequence should be distinct.
The sequence should be of length 'N'.
Each element should have a value between 1 to 60000. 
Let 'M' denote the sum of all the elements of the sequence and 'K' be the gcd of all the elements of the sequence then 'K' should be equal to 1 and for each element, 'A[i]' (0 <= i < 'N') gcd of 'A[i]' and 'M' should not be equal to 1.

Return any cool sequence in any order. If an answer exists, the output will be 1, otherwise the output will be 0. Nonetheless, if an answer exists, return the sequence, otherwise return -1 in an array.

Note : Assume 0-based indexing.

For example: 
Let 'N' = 3.
'A' = {2, 3, 63} satisfies all the conditions of the cool sequence.
Detailed explanation ( Input/output format, Notes, Images )
Input Format:- 
The first line contains an integer 'T', which denotes the number of test cases.
For every test case:-
The first line contains only one integer 'N', denoting the number of elements of the cool sequence.
Output Format:- 
For each test case, Return 'N' space-separated integers denoting the elements of the cool sequence in any order.
Note:- 
You don’t need to print anything. Just implement the given function. 1 in the output denotes the correct sequence and 0 denotes the wrong sequence.
Constraints:- 
1 <= 'T' <= 10
1 <= 'N' <= 40000

Time Limit: 1 sec
Sample Input 1:-
2
6
7
Sample Output 1:-
1
1
Explanation of sample input 1:-
First test case:-    

'A' = {2, 3, 4, 8, 9, 10} has 'K' = 1 and gcd of each element with 'M' is not equal to 1.

Second test case:-
'A' = {2, 3, 4, 6, 8, 9, 10} has 'K' = 1 and gcd of each element with 'M' is not equal to 1.
Sample Input 2:-
2
4
10
Sample Output 2:-
1
1
Hint

Looking at the tight constraints we can observe that we actually need two-thirds of numbers between 1 and N.

Approaches (1)
Maths

Approach:-


Looking at the tight constraints we can observe that we actually need two-thirds of numbers between 1 and N. The main idea is that if we pick 'M' to be a multiple of some small primes 'X', then we just have to make sure that each element of the array is divisible by the 'X' and 'K' = 1. Based on the above idea we can choose 'M' = 6q, for some integer q and we will choose the elements of the cool sequence as multiples of 2 or 3 and we will definitely choose 2 and 3 to make sure that 'K' always remains 1. The constraints also hint towards this approach as there exist exactly two third numbers that are multiples of 2 or 3 between 1 and N. After taking all the numbers of the sequence as multiples of 2 or 3, it might be possible that the sum is not divisible by 6. The sum can be of the form 6q+2, 6q+3, 6q+5, 6q.

We can handle each case separately.

  • If the sum is of form 6q+2, then we will remove 8 from our sequence and add the next multiple of 6 into it.
  • If the sum is of form 6q+3, then we will remove 9 from our sequence and add the next multiple of 6 into it.
  • If the sum is of form 6q+5, then we will remove 9 from our sequence and add the next multiple of 6q+4 into it.

The above approach only works for numbers for 'N' > 5. For 'N' = 3, 4, 5 we can take {2, 3, 63}, {2, 3, 9 10}, and {2, 3, 6, 9, 10} respectively.

 

 Algorithm:-
 

  • Declare an unordered set of integer type 'vec' to store the sequence.
  • If 'N' == 3
    • Update 'vec' to {2, 5, 63}.
  • Else if 'N' == 4
    • Update 'vec' to {2, 3, 9, 10}.
  • Else if 'N' == 5
    • Update 'vec' to {2, 3, 6, 9, 10}.
  • Else
    • Initialize an integer 'current' to 0 to store the numbers to be inserted.
    • Initialize an integer 'sum' to 0 to store the sum of the sequence.
    • Iterate from 'i' = 0 to 'N'.
      • If 'current % 6' is equal to 0
        • Increment 'current' by 2.
      • Else if 'current % 6' is equal to 2
        • Increment 'current' by 1.
      • Else if 'current % 6' is equal to 3
        • Increment 'current' by 1.
      • Insert 'current' into 'vec'.
      • Update 'sum' by 'current'.
    • Increment 'current' by 1.
    • If 'sum % 6' is equal to 2
      • Erase '8' from 'vec'.
      • Run a while loop until 'current' is not divisible by 6.
        • Increment 'current' by 1.
      • Insert 'current' into 'vec'.
    • Else if 'sum % 6' is equal to 3
      • Erase '9' from 'vec'.
      • Run a while loop until 'current' is not divisible by 6.
        • Increment 'current' by 1.
      • Insert 'current' into 'vec'.
    • If 'sum % 6' is equal to 5
      • Erase '9' from 'vec'.
      • Run a while loop until 'current % 6' is not equal to 4.
        • Increment 'current' by 1.
      • Insert 'current' into 'vec'.
    • Declare a vector 'ans' to store the answer.
    • Iterate from it = 'vec.begin()' to 'vec.end()'.
      • Insert the current element into 'ans'.
    • Return 'ans'.


 

Time Complexity

O(N). Where 'N' is the number of elements in the cool sequence.

We are running a for loop over 'N' elements. Therefore the time complexity will be O(N).

Space Complexity

O(N). Where 'N' is the number of elements in the cool sequence.

We are using a vector of size 'N' to store the answer.  Therefore the space complexity is O(1).

Code Solution
(100% EXP penalty)
Cool sequences
Full screen
Console