מיון מערך k-מודולו

הגדרה: מערך הוא מערך k-מודולו ממוין אם הוא מסודר כך שלכל שני אינדקסים i, j מתקיים שאם i < j אזי:

arr[i] mod k ≤ arr[j] mod k (פעולת mod היא פעולת השארית שמתבצעת על-ידי האופרטור % ב-Java).

נתון מערך של מספרים שלמים a, ומספר טבעי k. יש למיין את המערך כך שיהיה k-מודולו ממוין.

לדוגמה, עבור המערך להלן, ועבור k = 10

012345678
35171325241287381

המערך הk-מודולו-ממוין יכול להיות:

012345678
81252133435177128

השיטה שתכתבו צריכה להיות יעילה ככל הניתן, גם מבחינת סיבוכיות הזמן וגם מבחינת סיבוכיות המקום.

אילוצים:

k הוא קבוע. למרות זאת, אסור להקצות מערך נוסף בשום גודל. גם לא בגודל k. גם לא להקצות רשימה מקושרת בגודל k או k משתנים בודדים, או כל מבנה נתונים אחר.

דוגמה 1:
קלט: 
a = [35, 17, 13, 252, 4, 128, 7, 3, 81],
k = 10
פלט: 
[81, 252, 13, 3, 4, 35, 17, 7, 128]

הסבר: המערך ממוין לפי שארית החלוקה ב-10.

דוגמה 2:
קלט: 
a = [10, 20, 30, 40, 50],
k = 10
פלט: 
[10, 20, 30, 40, 50]

הסבר: כל המספרים נותנים שארית 0 ולכן הסדר נשמר.

דוגמה 3:
קלט: 
a = [5, 15, 25, 35, 45],
k = 10
פלט: 
[5, 15, 25, 35, 45]

הסבר: כל המספרים נותנים שארית 5 ולכן הסדר נשמר.

דוגמה 4:
קלט: 
a = [1, 2, 3, 4, 5],
k = 3
פלט: 
[3, 1, 4, 2, 5]

הסבר: המספרים ממיונים לפי שארית החלוקה ב-3.

דוגמה 5:
קלט: 
a = [9, 8, 7, 6, 5],
k = 4
פלט: 
[8, 9, 5, 6, 7]

הסבר: המספרים ממיונים לפי שארית החלוקה ב-4.

דוגמה 6:
קלט: 
a = [100, 200, 300, 400, 500],
k = 100
פלט: 
[100, 200, 300, 400, 500]

הסבר: כל המספרים נותנים שארית 0 ולכן הסדר נשמר.

דוגמה 7:
קלט: 
a = [11, 22, 33, 44, 55],
k = 11
פלט: 
[11, 22, 33, 44, 55]

הסבר: כל המספרים נותנים שארית 0 ולכן הסדר נשמר.

דוגמה 8:
קלט: 
a = [2, 4, 6, 8, 10],
k = 2
פלט: 
[2, 4, 6, 8, 10]

הסבר: כל המספרים נותנים שארית 0 ולכן הסדר נשמר.

Loading...
נשמרLn 1, Col 1

קלט:

a = [35, 17, 13, 252, 4, 128, 7, 3, 81],
k = 10

הפלט המבוקש:

[81, 252, 13, 3, 4, 35, 7, 17, 128]