... המספר הגדול ביותר. ורק אחר כך לעבור על כל הערכים להגדיל אותם וכולי. אבל זאת לא כל האמת. כי בפועל,
אפשרי לרוץ פעם אחת על כל הרשימה ולבצע בריצה אחת את הפעולות הבאות: 1 - לנסות לאתר כל המספר ... לכאורה עלינו לבצע את הפעולות הבאות: (5-2=3) + (5-3=2) + (5-3=2) + (5-3=2) = 9 פעולות אבל מצד האמת,
אפשרי לחשב זאת גם כך: (5 5 = 25) דהיינו, המקסימאלי שהיה אם כל הערכים היו זהים לערך הגדול ... הגדלה כפולה של שני ערכים בבת אחת. ומכאן נובעת רמת הקושי הבאה של השאלה, שהיא, שיש לנו עוד חישוב
אפשרי , לחשב, במידה ונבצע X הגדלות כפולות, כמה Y הגדלות בודדות נבצע. דהיינו, אם יש לנו צורך ... ניגשים לפתור את החלק הזה של השאלה? אז לשם כך לכאורה בעצם עלינו לקחת רשימה, לחשב את כל האפשרויות
האפשריות להגדיל את הרשימה למקסימום. באמצעות כל השילובים של הגדלה בודדת ושל הגדלה כפולה. ומכאן ... היה יותר קל לחשב את העלות. דהיינו, אם ננתח את כל האפשרויות, נראה שבסופו של דבר, יש רק 3 אפשרויות
אפשריות. שהן: מבחינת המחיר שנשלם: 1 - זה לא משנה אם נבצע הגדלה בודדת או הגדלה כפולה. 2 - זה כן ... הבאה (1,2) דהיינו, שאנחנו צריכים להגדיל את 1 לערך 2. האם ניתן לבצע זאת בהגדלה כפולה? כמובן שלא.
אפשרי לבצע זאת בהגדלה אחת בודדת בלבד. ואם יש לנו את הרשימה (1, 100) דהיינו, שאנחנו צריכים ... 10, פחות הסכום שלהם שהוא 35, יוצא 35 שזאת כמות ההגדלות שצריכים לבצע. ועכשיו נראה שיש לנו 3 מצבים
אפשריים בלבד: אפשרות 1 - שכמות ההגדלות שאנחנו צריכים לבצע על MIN כדי להביא אותו ל MAX, הכמות ... כל שאר המספרים שצריכים להביא אותם אל MAX, בהתאם לחישובים לעיל. ואחרי שהבנו את כל זה, עכשיו נראה
שאפשרי לעשות את כל זה, בזמן ריצה של O(N). דהיינו, בריצה אחת בלבד. ואיך? נרוץ פעם אחת על כל ...