מערך של מספרים שלמים חיוביים נקרא "מערך ממוין לפי שארית של 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). הערת תוכן — תיקון חילוץ: שני מערכי הדוגמה בקובץ המקור (PDF) נשלפו במהופך (תופעת RTL ידועה בחילוץ טקסט מסמכי מקור בעברית) — סדרם המתוקן (התואם את הכלל המילולי, ואומת בהרצה בפועל) הוא כפי שמופיע כאן.
מערך של מספרים שלמים חיוביים נקרא "מערך ממוין לפי שארית של 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). הערת תוכן — תיקון חילוץ: שני מערכי הדוגמה בקובץ המקור (PDF) נשלפו במהופך (תופעת RTL ידועה בחילוץ טקסט מסמכי מקור בעברית) — סדרם המתוקן (התואם את הכלל המילולי, ואומת בהרצה בפועל) הוא כפי שמופיע כאן.
כתבו פעולה המקבלת מערך של מספרים שלמים חיוביים arr ומספר שלם חיובי k, ובודקת אם הוא "מערך ממוין לפי שארית של k". אם כן — הפעולה תחזיר ערך true, ואם לא — הפעולה תחזיר ערך false. הערה: כותרת הפעולה אינה מודפסת בשאלון — נבחר השם isSortedByRemainder(int[] arr, int k).
כתבו פעולה המקבלת מערך של מספרים שלמים חיוביים arr ומספר שלם וחיובי k. הפעולה תחזיר מערך חדש "הממוין לפי k", הכולל את כל הערכים של המערך arr. הערה: כותרת הפעולה אינה מודפסת בשאלון — נבחר השם buildSortedByRemainder(int[] arr, int k).
מהן סיבוכיות זמן הריצה של הפעולות שכתבתם בסעיפים א' ו-ב'? הסבירו את תשובתכם.
שאלות ותגובות על השאלה
🎓 לא הבנתם משהו? קבלו הסבר נוסף ממרצה לתכנות
שאלו כאן — ותקבלו מענה מוסמך.