לפניכם מספר פעולות המוגדרות על המחסנית:

• public static int NumOf(Stack<int> m) – הפעולה מחזירה מספר איברים במחסנית m.
• public static int RandChoice(Stack<int> m) – הפעולה מחזירה איבר שנבחר באקראי מתוך מחסנית m.
• public static Stack<int> CreateSmall(Stack<int> m, int a) – הפעולה מקבלת מחסנית m המכילה מספרים שלמים וערך a, ומחזירה מחסנית חדשה המכילה את כל המספרים מתוך m הקטנים מ-a.
• public static Stack<int> CreateLarge(Stack<int> m, int a) – הפעולה מקבלת מחסנית m המכילה מספרים שלמים וערך a, ומחזירה מחסנית חדשה המכילה את כל המספרים מתוך m הגדולים מ-a.
• public static void EraseSmalls(Stack<int> m, int k) – הפעולה מוחקת ממחסנית m את k האיברים הקטנים ביותר. הנחה: במחסנית יש לפחות k איברים.
• public static void EraseLarges(Stack<int> m, int k) – הפעולה מוחקת ממחסנית m את k האיברים הגדולים ביותר. הנחה: במחסנית יש לפחות k איברים.

נתונה פעולה רקורסיבית What המשתמשת בפעולות הנ"ל. הפעולה מקבלת מחסנית s, המכילה מספר אי-זוגי של מספרים שלמים שכולם שונים זה מזה:

public static int What(Stack<int> s) {
    int a = RandChoice(s);
    Stack<int> m1 = CreateSmall(s,a);
    int k1 = NumOf(m1);
    Stack<int> m2 = CreateLarge(s,a);
    int k2 = NumOf(m2);
    if (k1 > k2) {
        EraseSmalls(m1, k2+1);
        return What(m1);
    }
    if (k2 > k1) {
        EraseLarges(m2, k1+1);
        return What(m2);
    }
    return a;
}

המחסנית s לסעיף א' (משמאל לימין: מראש המחסנית לתחתיתה):

ראש המחסנית → 43, -3, 8, 9, 12, -9, 7, 3, 1 ← תחתית המחסנית