Q An array of size k contains integers between 1 and n. You are given an additional scratch array of size n. Compress the original array by removing duplicates in it. What if k << n?

ANS : I solved the problem.But i want to solve the problem in O(k) time with out using auxiliary array can any one plz help me out .....