מערך של מספרים שלמים חיוביים נקרא "מערך ממוין לפי שארית של k" אם הוא עונה על הכלל: בתחילת המערך מופיעים מספרים שמתחלקים ב-k ללא שארית (שארית 0), אחריהם מספרים עם שארית 1, אחריהם עם שארית 2, וכן הלאה — קבוצות רצופות בסדר שאריות עולה, בלי דרישת סדר בין איברי אותה קבוצה. לדוגמה, המערך 4, 8, 1, 13, 9, 2, 7, 15 ממוין לפי שארית של 4 (שאריות: 0,0,1,1,1,2,3,3). המערך 15, 1, 2, 7, 13, 8, 4, 9 ממוין לפי שארית של 5 (שאריות: 0,1,2,2,3,3,4,4).

כתבו פעולה המקבלת מערך של מספרים שלמים חיוביים arr ומספר שלם חיובי k, ובודקת אם הוא "מערך ממוין לפי שארית של k". אם כן — הפעולה תחזיר ערך true, ואם לא — הפעולה תחזיר ערך false. הערה: כותרת הפעולה אינה מודפסת בשאלון — נבחר השם isSortedByRemainder(int[] arr, int k).

כתבו פעולה המקבלת מערך של מספרים שלמים חיוביים arr ומספר שלם וחיובי k. הפעולה תחזיר מערך חדש "הממוין לפי k", הכולל את כל הערכים של המערך arr. הערה: כותרת הפעולה אינה מודפסת בשאלון — נבחר השם buildSortedByRemainder(int[] arr, int k).

מהן סיבוכיות זמן הריצה של הפעולות שכתבתם בסעיפים א' ו-ב'? הסבירו את תשובתכם.