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