המספר הגדול הבא

לפני שבועיים התחלתי להרגיש שאני מתגעגעת לפתירת “שאלות ראיונות“. מאז שהתחלתי את העבודה החדשה שלי יצא לי להתעסק בהמון נושאים מרתקים וכיפיים, אבל לא בפתירת חידות אלגוריתמיות פשוטות. 

אני בטוחה שלפחות חלקכן תסכימו איתי שלפתור את החידות האלו זה ממש כיף. הן לא קשות מדי, הן מפעילות את המוח, והן עוזרות לתרגל פונקציונליות בסיסית של השפה האהובה עלינו, או ללמוד בצורה נעימה שפות חדשות.

כיוון שהתחלתי להתגעגע, החלטתי להתחיל לפתור כמה שאלות כאלה בשבוע. את השאלות שפתרתי העליתי לעמוד הפייסבוק של מאיה כותבת אלגוריתמים עם התגית #קודבצהריים (כנסו ותיהנו).
המטרה הראשונית הייתה להעלות שאלות קלילות, כאלו שמאתגרות אותנו, אבל לא יותר מדי, כי חם בחוץ והמוח של כולנו גם ככה דייסה. אבל, איך לא – השאלה השנייה שהעליתי רק נראתה קלה, ובפועל הייתה יותר קשה ממה שהערכתי. 

לא הצלחתי לפתור אותה בצהריים של הפרסום אבל מאוחר יותר בערב נפל לי האסימון. חוץ ממני גם הרבה מהמגיבות והמגיבים הרגישו שהשאלה מאתגרת, ולכן חשבתי שמדובר בהזדמנות מצוינת לכתוב פוסט אלגוריתמים מהסוג שלא פתרתי כבר המון זמן.

מוכנות? בואו נתחיל.
השאלה לקוחה מהאתר המגניב מאוד CodeWars. אם אתן רוצות לנסות לפתור אותה בעצמכן לפני שאתן מסתכלות על הפתרון, עצרו עכשיו ורוצו לשם.

אני אתחיל בהצגת השאלה –
בהינתן מספר N, המשימה היא למצוא את המספר הבא אחרי N שמורכב מאותן הספרות. אם לא קיים מספר כזה, צריך להחזיר 1-.

דוגמאות – 

nextBiggerNumber(12) = 21
nextBiggerNumber(513) = 531
nextBiggerNumber(111) = -1

טוב, נשמע פשוט.האינסטינקט הראשוני שלי לגבי השאלה הזו היה שאני יכולה פשוט לייצר את כל הפרמוטציות של הספרות של N, ולהחזיר את התוצאה המינימלית שגדולה מ-N. 

אין ספק שזה היה עובד, אבל הסיבוכיות של פתרון כזו היא מזעזעת. מעבר על כל הפרמוטציות של מספר N שיש בו x ספרות היא o(x!). כלל אצבע טוב הוא ש-99% מהפעמים [יש יוצאים מן הכלל, כמובן] אם התשובה שלך היא בסיבוכיות עצרת של אורך הקלט היא כנראה לא נכונה.

אוקי, המשכתי האלה. המחשבה הבאה שלי הייתה כזו – בהינתן מספר כלשהו N, אם אני רוצה למצוא מספר אחר שגדול ממנו ומורכב מאותן הספרות אני צריכה למצוא שתי ספרות ב-N כך שהספרה השמאלית יותר קטנה יותר מהספרה הימנית יותר ולהחליף ביניהן.

לדוגמא, נגיד והמספר שלי הוא – 

N = 123

אני אבחר בשתי הספרות השמאליות ביותר – 1 ו-2. הספרה 1 נמצאת משמאל לספרה 2 והיא קטנה ממנה. אם אני אחליף בין הספרות אני אקבל את המספר 213 שהוא אכן גדול יותר מהמספר המקורי שלי 123.

למה זה עובד? תחשבו רגע על הייצוג של מספר דצימלי.
במספר 123, למשל, 3 הוא ספרת האחדות, 2 הוא ספרות העשרות ו-1 הוא ספרת המאות.
מה זה אומר? שהמספר 123 מורכב כך – 

N = 123 = 1*100 + 2*10 + 3*1

כל ספרה במספר דצימלי מייצגת את המקדם של עשר בחזקת המיקום של הספרה – 

N = 123 = 1*102 + 2*101 + 3*100

כיוון שככל שהולכים שמאלה במספר גדלה החזקה של עשר, וכך גם והערך של ההכפלה.
כלומר – ככל שהספרה שמאלית יותר במספר, ככה ההשפעה שלה על גודל המספר הוא משמעותי יותר, לכן אם אני מחליפה בין ספרות מספר באופן שגורם לספרה השמאלית יותר להיות גדולה יותר, סכום המכפלות יוצא גדול יותר.

N = 123 = 1*100 + 2*10 + 3*1 < 2*100 + 1*10 + 3*1 = 213

אוקי, אז הבנתי שכל מה שאני צריכה לעשות כדי למצוא מספר גדול יותר מ-N הוא למצוא שתי ספרות כפי שתיארתי למעלה ולהחליף ביניהן. אבל זה עדיין לא מספיק. השאלה לא ביקשה למצוא סתם מספר גדול יותר, אלא את המספר הגדול הבא – כלומר, המינימלי מבין המספרים הגדולים יותר.
במקרה של הדוגמא שלי, המספר אליו הגעתי, 213 אכן גדול יותר מ-123, אבל הוא לא המספר הבא אחריו. המספר 132 הוא המספר הקטן ביותר שגדול מ-123 ומורכב מאותן הספרות, ולכן הוא המספר הבא.
אז מה אני עושה עכשיו? איך אני מוצאת את המספר הגדול הבא?

אני יודעת שככל שהספרה נמצאת ימינה יותר במספר, כך ההשפעה שלה קטנה יותר. כלומר, אם אני רוצה להגדיל את המספר הכי מעט שאני יכולה, אני צריכה להחליף את הספרות הכי ימניות.
מגניב, אני אכתוב את האלגוריתם הזה. 

def nextBigger(n):
	digits = [int(d) for d in str(n)]
	for i in range(len(digits)-2, -1, -1):
		for j in range(len(digits)-1, i, -1):
			if digits[i] < digits[j]:	
				digits[i], digits[j] = digits[j], digits[i]
				return int(‘’.join(digits))
	return -1

נראה טוב!

אני אנסה להריץ כמה דוגמאות.

nextBigger(123):
    digits = [1,2,3]
    i = 1
    j = 2
    digits[1] < digits[2] → True (2<3)
    return 132

ווהו! קיבלתי תוצאה נכונה.

אני אנסה עוד דוגמא.

nextBigger(144):
    digits = [1,4,4]
    i = 1
    j = 2
    digits[1] < digits[2] → False (4=4)
    i = 0
    j = 2
    digits[1] < digits[2] → True (1<4)
    return 441

אוי, קיבלתי תוצאה לא נכונה.
המספר המתאים הבא אחרי 144 הוא 414, לא 441.

למה זה קרה?
זה קרה בגלל שההחלפה שעשיתי אכן נתנה לי את ההגדלה המינימלית שיכולתי לעשות בעזרת החלפה אחת אבל לא את ההגדלה המינימלית שיכולתי להשיג עם פרמוטציה כלשהי, כפי שהשאלה ביקשה.
כדי להגיע למספר המינימלי הבא במקרה של 144 הייתי צריכה להחליף את שתי הספרות השמאליות ביותר, אבל ראיתי שבדוגמא של 123 אסטרטגיה כזאת דווקא לא הייתה עובדת.
אני צריכה למצוא אלגוריתם חדש שיכסה את כל המקרים.

פה אני מודה שנתקעתי. ניסיתי לחשוב על כל הדרכים והצורות בהן אני יכולה להבטיח שההחלפה (או סדרת החלפות) שאני אעשה באמת תביא את התוצאה המינימלית, ולא הצלחתי למצוא את התשובה.
רק כמה שעות מאוחר יותר (מדהים איך המוח שלנו מעבד דברים ברקע) פתאום נפל לי האסימון.
מה בעצם קרה פה?

האלגוריתם שבו השתמשתי החליף את שתי הספרות הראשונות שהוא מצא שקיימו את התנאי שלי. כלומר, בהינתן סדר הספרות ההתחלתי לא היו שתי ספרות שהוא היה יכול להחליף והיו נותנות תוצאה קטנה יותר.
לדוגמא, במספר – 

N = 123456

הספרות הראשונות שאני יכולה להחליף הן 5 ו-6. החלפה כזו תיתן את התוצאה – 

NB = 123465

ההחלפה שעשיתי הגדילה את המספר המקורי ב-9.
לא הייתה אף החלפה אחרת שיכולתי לעשות שהייתה מגדילה את המספר N פחות, כי כל החלפה אחרת הייתה נותנת לאחת המכפלות הגדולות יותר מקדם גבוה יותר.

A = 123654 - N = 198
B = 126453 - N = 2997

וכן הלאה…

אבל, אחרי שעשיתי את ההחלפה, והגדלתי את המספר, עכשיו אני צריכה להקטין אותו עד שהוא יהיה המספר הכי קטן שהוא עדיין יותר גדול מהמספר המקורי – כפי שהשאלה ביקשה.
למשל, בדוגמא הבאה –  

N = 1144

אחרי החלפה אחת אני אקבל את המספר – 

NB = 1441

המספר החדש אכן יותר גדול מהמספר המקורי אבל אפשר להקטין אותו כך שהוא עדיין ישאר יותר גדול.
איך אני עושה את זה?

אני אנסה להסביר את זה בצורה הכי אינטואיטיבית שאני יכולה.
נניח והייתי מפרקת את NB לסכום שני מספרים  – 

NB = 1400 + x

מכיוון שמתקיים – 

N < 1400

אז זה לא משנה מה הערך של x. כל ערך שניתן לו (שאיננו שלילי) יקיים את המשוואה – 

N < 1400 + x

במספר שהגעתי אליו אחרי החלפה אחת מתקיים  –

x = 41

אם אני אצליח להקטין את x, אני אקבל בוודאות מספר שהוא עדיין גדול מ-N אבל גם קטן מ-NB.
כדי לקבל את המספר הקטן ביותר האפשרי אני אמיין את הספרות בסדר עולה משמאל לימין. זה עובד, כי אחרי מיון ככל שהחזקה גבוהה יותר כך המקדם שלה יהיה נמוך יותר.

sorted(x) = 14

כעת, אחבר את x ל-1400 ואקבל את התוצאה הקטנה ביותר האפשרית – 

NB’ = 1414

עכשיו אני יכולה להיות בטוחה שאין אף החלפה שתקטין את NB’ ועדיין תשאיר את המספר גדול יותר מהמספר המקורי N.
אני אוסיף את התיקון לאלגוריתם שלי!

def nextBigger(n):
	digits = [int(d) for d in str(n)]
	for i in range(len(digits)-2, -1, -1):
		for j in range(len(digits)-1, i, -1):
			if digits[i] < digits[j]:	
				digits[i], digits[j] = digits[j], digits[i]
				digits[i+1:] = sorted(digits[i+1:])
				return int(‘’.join(digits))
	return -1

זהו.

אני ממש מקווה שזה יצא ברור, תרגישו חופשיות להעיר אם משהו לא הגיוני ותפתרו המון חידות, זה כיף!