שחזורי ראיונות עבודה -> האם מספר הוא חזקה של 2? (מחפש פיתרון שונה מ- x & (x-1) i
- האם מספר הוא חזקה של 2? (מחפש פיתרון שונה מ- x & (x-1) i
-
ע"י: שלומישלום זו שאלה די פופולרית , ואני מכיר את הפיתרון שפועל בזמן קבוע, אך מישהו יודע מה בדיוק הפיתרון היותר טריוויאלי? אני יודע שבגדול זה לחלק את המספר ב-2 שוב ושוב עד שמגיעים ל-0 , אך אני זוכר שיש משהו קצת יותר יעיל מזה (אותו כיוון רק עם איזשהו שיפור) אך אני לא מצליח להיזכר בדיוק. מישהו יודע? (אם אני לא טועה זה נוגע לשורשים או משהו כזה, אני פשוט לא מצליח לחשוב על פיתרון חוץ ממה שציינתי) תודה מראשע"י: 1_אורח_כלליאפשר לעבור על כל ביטי המספר ולבדוק אם רק אחד מהם דלוק, זה בסיבוכיות O של n. אםשר לעשות חיפוש בינארי אחר ה msb (תחשוב איך) בסיבוכיות O של logn. ובהינתן ה msb תחשוב איך אתה מוודא שהמספר שלך הוא חזקה של 2. לא הבנתי איך לעשות חיפוש בינרי? התכוונת לזה: מיון - O(nlogn) חיפוש - O(log n) הסכום שלהם גדול מ O(n) ככה שעדיף כבר לעבור בצורה סדרתית על כל הביטים. לא מספיק למצוא את הmsb צריך לוודא שאין אחריו עוד ביטים שהם לא 0. תודהע"י: 1_אורח_כלליאורח יש לך טעות אתה מדפיס אם המספר זוגי או לא.ע"י: 1_אורח_כלליהפיתרון הפשוט הוא לחסר 1 ולבצע AND על הביטים של התוצאה והספר המקורי. במידה ונקבל 0 המספר הוא חזקה של 2.ע"י: 1_אורח_כלליפתרון נוסף זה להחזיק מערך עם כל האפשרויות ואז הגישה אליו היא ב- O(1).ע"י: 1_אורח_כלליאפשר לעבור על כל ביטי המספר ולבדוק אם רק אחד מהם דלוק, זה בסיבוכיות O של n. אםשר לעשות חיפוש בינארי אחר ה msb (תחשוב איך) בסיבוכיות O של logn. ובהינתן ה msb תחשוב איך אתה מוודא שהמספר שלך הוא חזקה של 2.ע"י: 1_אורח_כללישלום זו שאלה די פופולרית , ואני מכיר את הפיתרון שפועל בזמן קבוע, אך מישהו יודע מה בדיוק הפיתרון היותר טריוויאלי? אני יודע שבגדול זה לחלק את המספר ב-2 שוב ושוב עד שמגיעים ל-0 , אך אני זוכר שיש משהו קצת יותר יעיל מזה (אותו כיוון רק עם איזשהו שיפור) אך אני לא מצליח להיזכר בדיוק. מישהו יודע? (אם אני לא טועה זה נוגע לשורשים או משהו כזה, אני פשוט לא מצליח לחשוב על פיתרון חוץ ממה שציינתי) תודה מראש