Last Updated: 18 Sep, 2022
Cool sequences
Ninja
Asked in company
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.
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
Approaches
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'.
- If 'current % 6' is equal to 0
- 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'.