Ninja Class

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
2 upvotes
Asked in company
Directi

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).
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
5 9
3 3
Sample Output 1 :
1 3 3 1 1
1 1 1
Explanation Of Sample Input 1 :
For test case 1 we have, 

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

Sum of elements = 1+3+3+1+1 = 9.

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

For test case 2 we have,

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

Sum of elements = 1+1+1 = 3.

LCM of elements = LCM ( 1, 1, 1 ) = 1 which is <= (3/2).
Sample Input 2 :
2
4 4
4 6
Sample Output 2 :
1 1 1 1
1 2 2 1
Hint

Try solving the problem for ‘N = 3’ first.

 

Approaches (1)
Optimal 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.

 

Time Complexity

O(N), where N is the number of integers that satisfy the given condition.
 

We are printing the ‘N’ integers that satisfy the conditions, so the overall time complexity is O(N).

 

Space Complexity

 

O(1)
 

Constant extra space is required. Hence, the overall Space Complexity is O(1).

Code Solution
(100% EXP penalty)
Ninja Class
Full screen
Console