You have integer array of length n ([1 2 1 2 1 3 1 3]).Remove all occurance of 1(array become [2 2 3 3]).Now you can append this resulting array to initial array , any number of time ([1 2 1 2 1 3 1 3 2 2 3 3]).
Given a resulting array print the initial array
eg.
input
1 2 1 2 1 3 1 3 2 2 3 3 2 2 3 3
output:
1 2 1 2 1 3 1 3
if no initial array possible print -1
if multiple ans possible print lexicographically smaller array.
Find the prime factorisation of N , Where N = size of the resulting array - No. Of 1’s in resulting array .
Let cnt be no. of 1’s in resultant array.
Let array B be an array which is resulting array - all occurence of 1’s.
Let last be the position of the last 1 in resulting array.
There can be atmost log(N) prime factors of N . Check that whether they can make the resultant array after repeating themselves if they do then insert them in set S. Now , the final length of array would be smallest no. >= Last - cnt ( let it be Y ), which is completely divisible by elements present in set S.
Now , just print prefix of resulting array of size Y+cnt.
Alternate solution can be of O(N*sqrt(N)) . Where we find the smallest factor of N >= last - cnt , which makes array B by repeating itself .