Modulo Sort

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 0.5s
Memory limit: 256M

Author:
Problem types

Given an array of non-negative integers M and positive integer K, sort the elements of the given array in the increasing order of their modulo with K. If two or more elements have the same remainder, sort the numbers numerically.

Input Specifications

You will receive three lines of input. The first line will contain positive integer N (1 \le N \le 10^5), the length of the array.

The next line will contain positive integer K (1 \le K \le 10^7), the number you are dividing by.

The final line will contain array M. The array M will contain N non-negative integers. The integers in M will never exceed 10^7.

Output Specifications

On a single line, output the sorted array with a single space between each number.

Subtasks

Subtask 1 [20%]

For 20% of the marks, K = 4.

Subtask 2 [20%]

For an additional 20% of the marks, K \le 10.

Subtask 3 [60%]

For full marks, there are no further constraints.

Sample Input 1

4
4
68 19 14 62

Sample Output 1

68 14 62 19

Explanation for Sample Output 1

The first number, 68 mod 4 = 0. The next numbers 14 and 62 mod 4 = 2. Because 14 < 62, 14 comes first. Finally, that leaves 19. It comes last because 19 mod 4 = 3.

Sample Input 2

8
4
1 18 21 27 17 4 4 16

Sample Output 2

4 4 16 1 17 21 18 27

Comments

There are no comments at the moment.