Last Updated: 26 Oct, 2021

Ninja Class

Moderate

Asked in company

Solve now

Problem statement

Ninja has recently learned to calculate the LCM of arrays and his teacher challenged him to solve a problem that no student was able to solve till now in the first attempt.

He gives two integers ‘N’ and ‘M’ and you need to find ‘N’ integers ‘A1’, ‘A2’, … , ‘AN’ such that :

A1 + A2 + … + AN = M

LCM ( A1, A2 , … , AN ) <= M/2

Here LCM is the least common multiple of numbers ‘A1’, ‘A2’, … , ‘AN’.

Output ‘N’ integers for which above conditions are satisfied. It is guaranteed that for given constraints, the answer always exists.

Example :

N = 4
M = 6

Explanation : 

One of the possible answers can be [ 1, 2, 2, 1].

Sum of elements = 1+2+2+1 = 6.

LCM of elements = LCM ( 1, 2, 2, 1 ) = 2 which is <= (6/2).

Input Format :

The first line contains an integer 'T' which denotes the number of test cases to be run. Then the test cases follow.

The only line of each test case contains two integers ‘N’ and ‘M’.

Output format :

For each test case, print ‘N’ integers satisfying the mentioned conditions.

Print the output of each test case in a new line.

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
3 <= M <= 10^9
3 <= N <= M

Time Limit : 1 sec

Solve now

Approaches

01 Approach

Approach :

We first try to solve the problem by fixing ‘N = 3’.
Now, let ‘M’ = odd.
Then we fix ‘A1’ = 1.
Now, we need to find ‘A2’ and ‘A3’ such that their sum is ‘M-1’ which is even.
If we take ‘A2’ = ‘M/2’ and ‘A3’ = ‘M/2’, then their sum will be ‘M-1’ as ‘M’ was odd.
Also, the LCM of ‘A1’, ‘A2’, ‘A3’ will be equal to ‘M/2’ which satisfies our condition.
So, ‘A1’ = 1, A2 = ‘M/2’ , ‘A3’ = ‘M/2’.
Let M = even.
Then ‘M’ >= 4 as constraints tell ‘M’ >=3.
So, we fix the first number, ‘A1’ as 2.
Now we need to find ‘A2’ and ‘A3’ such that their sum is ‘M-2’.
So these can be ‘M/2 - 1’ each.
But if ‘M’ is a multiple of 4, then the LCM of ‘M/2 - 1’ and ‘2’ can exceed ‘M/2’.
So, the above is only valid for the case when ‘M’ is even but not divisible by 4 as then ‘M/2’ will be odd and ‘M/2 - 1’ will be even and thus we will get LCM of ‘M/2 - 1’.
Now the only case left is when ‘M’ is divisible by 4.
Then the numbers can be ‘M/2’, ‘M/4’ and ‘M/4’ respectively with LCM = M/2.
Now let us solve for ‘N’ > 3.
We will reuse the above solution for ‘N=3’.
We fix the ‘N-3’ numbers equal to 1.
So, we want A1 + A2 + … AN = ‘M’.
A1 + A2 + A3 + ( 1 + 1 + … + 1) = M.
A1 + A2 + A3 + (N-3) = M.
A1 + A2 + A3 = M - N + 3.
Now, we find ‘A1’, ‘A2’ and ‘A3’ such that their LCM <= ( M-N+3)/2 <= M/2 and A1 + A2 + A3 = M-N+3.
We find these values as described above.

Algorithm :

Initialise an array ‘ans’ of size ‘N’.
Call the function ‘solve3’ with parameter ‘M-N+3’.
Let ‘K’ = ‘M-N+3’.
If ‘K’ is odd :
Return an array with elements 1, K/2 and K/2.
If ‘K’ is even but not divisible by 4 :
Return an array with elements 2, K/2 - 1 and K/2 - 1.
If ‘K’ is divisible by 4 :
Return an array with elements K/2, K/4 and K/4.
Store the array returned by ‘solve3’ in array ‘v’.
Run a for loop from ‘i = 0’ to ‘i = N-1’ :
If ‘i<=2’ , store ‘v[i]’ in ‘ans[i]’.
Else, store 1 in ‘ans[i]’.
Return the ‘ans’ as final result.

Solve now