ה-1 ברציפות הארוכות ביותר בייצוג בינארי
ניתן מספר נ המשימה היא למצוא את האורך של הארוך ביותר ברציפות 1 שניות סדרה בייצוג הבינארי שלה.
דוגמאות:
קֶלֶט: n = 14
תְפוּקָה: 3
הֶסבֵּר: הייצוג הבינארי של 14 הוא 111 0.קֶלֶט: n = 222
תְפוּקָה: 4
הֶסבֵּר: הייצוג הבינארי של 222 הוא 110 1111 0.
תוכן עניינים
- [גישה נאיבית] זמן איטרטיבי O(1) ומרחב O(1)
- [גישה יעילה] שימוש במניפולציה של סיביות O(1) זמן ו-O(1) מרחב
- [גישה נוספת] באמצעות המרת מחרוזת
[גישה נאיבית] זמן איטרטיבי O(1) ומרחב O(1)
C++ #include using namespace std ; int maxConsecutiveOne ( int n ){ int count = 0 ; int maxi = 0 ; // traverse and check if bit set increment the count for ( int i = 0 ; i < 32 ; i ++ ){ if ( n & ( 1 < < i )){ count ++ ; } else { maxi = max ( maxi count ); count = 0 ; } } return maxi ; } int main () { int n = 14 ; cout < < maxConsecutiveOne ( n ) < < 'n' ; return 0 ; }
Java public class GFG { static int maxConsecutiveOne ( int n ) { int count = 0 ; int maxi = 0 ; // traverse and check if bit set increment the count for ( int i = 0 ; i < 32 ; i ++ ) { if (( n & ( 1 < < i )) != 0 ) { count ++ ; } else { maxi = Math . max ( maxi count ); count = 0 ; } } return maxi ; } public static void main ( String [] args ) { int n = 14 ; System . out . println ( maxConsecutiveOne ( n )); } }
Python def maxConsecutiveOne ( n ): count = 0 maxi = 0 # traverse and check if bit set increment the count for i in range ( 32 ): if n & ( 1 < < i ): count += 1 else : maxi = max ( maxi count ) count = 0 return maxi if __name__ == '__main__' : n = 14 print ( maxConsecutiveOne ( n ))
C# using System ; class GFG { static int MaxConsecutiveOne ( int n ) { int count = 0 ; int maxi = 0 ; // traverse and check if bit set increment the count for ( int i = 0 ; i < 32 ; i ++ ) { if (( n & ( 1 < < i )) != 0 ) { count ++ ; } else { maxi = Math . Max ( maxi count ); count = 0 ; } } return maxi ; } static void Main () { int n = 14 ; Console . WriteLine ( MaxConsecutiveOne ( n )); } }
JavaScript function maxConsecutiveOne ( n ) { let count = 0 ; let maxi = 0 ; // traverse and check if bit set increment the count for ( let i = 0 ; i < 32 ; i ++ ) { if ( n & ( 1 < < i )) { count ++ ; } else { maxi = Math . max ( maxi count ); count = 0 ; } } return maxi ; } // Driver code let n = 14 ; console . log ( maxConsecutiveOne ( n ));
תְפוּקָה
3
[גישה יעילה] שימוש במניפולציה של סיביות O(1) זמן ו-O(1) מרחב
הרעיון מבוסס על התפיסה שה- ו של רצף סיביות עם a שמאלה מוזז ב-1 גרסה של עצמה מסירה ביעילות את הנגרר 1 מכל רצף של רצופות 1 שניות .
אז המבצע נ = (n & (n < < 1)) מקטין את האורך של כל רצף של 1 שניות על ידי אחד בייצוג בינארי של נ . אם נמשיך לעשות את הפעולה הזו בלולאה, בסופו של דבר נ = 0. מספר האיטרציות הנדרשות כדי להגיע הוא למעשה אורך הרצף הארוך ביותר ברציפות של 1 שניות .
אִיוּר:
בצע את השלבים הבאים כדי ליישם את הגישה לעיל:
- צור ספירת משתנים עם ערך .
- הפעל לולאת זמן עד נ אינו 0.
- בכל איטרציה בצע את הפעולה נ = (n & (n < < 1))
- הגדל את הספירה באחד.
- ספירת החזרות
#include using namespace std ; int maxConsecutiveOnes ( int x ) { // Initialize result int count = 0 ; // Count the number of iterations to // reach x = 0. while ( x != 0 ) { // This operation reduces length // of every sequence of 1s by one. x = ( x & ( x < < 1 )); count ++ ; } return count ; } int main () { // Function Call cout < < maxConsecutiveOnes ( 14 ) < < endl ; return 0 ; }
Java class GFG { private static int maxConsecutiveOnes ( int x ) { // Initialize result int count = 0 ; // Count the number of iterations to // reach x = 0. while ( x != 0 ) { // This operation reduces length // of every sequence of 1s by one. x = ( x & ( x < < 1 )); count ++ ; } return count ; } public static void main ( String strings [] ) { System . out . println ( maxConsecutiveOnes ( 14 )); } }
Python def maxConsecutiveOnes ( x ): # Initialize result count = 0 # Count the number of iterations to # reach x = 0. while ( x != 0 ): # This operation reduces length # of every sequence of 1s by one. x = ( x & ( x < < 1 )) count = count + 1 return count if __name__ == '__main__' : print ( maxConsecutiveOnes ( 14 )) # by Anant Agarwal.
C# using System ; class GFG { // Function to find length of the // longest consecutive 1s in binary // representation of a number private static int maxConsecutiveOnes ( int x ) { // Initialize result int count = 0 ; // Count the number of iterations // to reach x = 0. while ( x != 0 ) { // This operation reduces length // of every sequence of 1s by one. x = ( x & ( x < < 1 )); count ++ ; } return count ; } // Driver code public static void Main () { Console . WriteLine ( maxConsecutiveOnes ( 14 )); } } // This code is contributed by Nitin Mittal.
JavaScript function maxConsecutiveOnes ( x ) { // Initialize result let count = 0 ; // Count the number of iterations to reach x = 0 while ( x !== 0 ) { // This operation reduces length of // every sequence of 1s by one x = ( x & ( x < < 1 )); count ++ ; } return count ; } // Driver code console . log ( maxConsecutiveOnes ( 14 ));
PHP // PHP program to find length function maxConsecutiveOnes ( $n ) { // Initialize result $count = 0 ; // Count the number of // iterations to reach x = 0. while ( $n != 0 ) { // This operation reduces // length of every sequence // of 1s by one. $n = ( $n & ( $n < < 1 )); $count ++ ; } return $count ; } echo maxConsecutiveOnes ( 14 ) ' n ' ; ?>
תְפוּקָה
3
מורכבות זמן: O(1)
מרחב עזר: O(1)
[גישה נוספת] באמצעות המרת מחרוזת
אנו מאתחלים שני משתנים max_len ו-cur_len ל-0. לאחר מכן אנו חוזרים על כל סיביות של המספר השלם n. אם הסיביות הכי פחות משמעותיות (LSB) היא 1, נגדיל את cur_len כדי לספור את הריצה הנוכחית של 1 רצופות. אם ה-LSB הוא 0 הוא שובר את הרצף הנוכחי אז אנו מעדכנים את max_len אם cur_len גדול יותר ומאפסים את cur_len ל-0. לאחר בדיקת כל סיביות נעביר את n ימינה ב-1 כדי לעבור לסיביות הבאות. לבסוף לאחר סיום הלולאה אנו מבצעים עדכון אחרון של max_len אם cur_len הסופי גדול יותר ומחזירים max_len כאורך הרצף הארוך ביותר של 1s עוקבות.
C++ #include #include #include using namespace std ; int maxConsecutiveOnes ( int n ){ string binary = bitset < 32 > ( n ). to_string (); int count = 0 ; int maxCount = 0 ; // Loop through the binary string to // find the longest consecutive 1s for ( int i = 0 ; i < binary . size (); i ++ ) { if ( binary [ i ] == '1' ) { count ++ ; if ( count > maxCount ) { maxCount = count ; } } else { count = 0 ; } } // Print the result return maxCount ; } int main () { int n = 14 ; cout < < maxConsecutiveOnes ( n ) < < 'n' ; return 0 ; }
Java import java.util.* ; public class Main { static int maxConsecutiveOnes ( int n ) { String binary = String . format ( '%32s' Integer . toBinaryString ( n )). replace ( ' ' '0' ); int count = 0 ; int maxCount = 0 ; // Loop through the binary string to // find the longest consecutive 1s for ( int i = 0 ; i < binary . length (); i ++ ) { if ( binary . charAt ( i ) == '1' ) { count ++ ; if ( count > maxCount ) { maxCount = count ; } } else { count = 0 ; } } // Return the result return maxCount ; } public static void main ( String [] args ) { int n = 14 ; System . out . println ( maxConsecutiveOnes ( n )); } }
Python def maxConsecutiveOnes ( n ): binary = format ( n '032b' ) count = 0 maxCount = 0 # Loop through the binary string to # find the longest consecutive 1s for bit in binary : if bit == '1' : count += 1 if count > maxCount : maxCount = count else : count = 0 # Return the result return maxCount if __name__ == '__main__' : n = 14 print ( maxConsecutiveOnes ( n ))
C# using System ; class GFG { static int MaxConsecutiveOnes ( int n ) { string binary = Convert . ToString ( n 2 ). PadLeft ( 32 '0' ); int count = 0 ; int maxCount = 0 ; // Loop through the binary string to // find the longest consecutive 1s foreach ( char bit in binary ) { if ( bit == '1' ) { count ++ ; if ( count > maxCount ) maxCount = count ; } else { count = 0 ; } } // Return the result return maxCount ; } static void Main () { int n = 14 ; Console . WriteLine ( MaxConsecutiveOnes ( n )); } }
JavaScript function maxConsecutiveOnes ( n ) { let binary = n . toString ( 2 ). padStart ( 32 '0' ); let count = 0 ; let maxCount = 0 ; // Loop through the binary string to // find the longest consecutive 1s for ( let i = 0 ; i < binary . length ; i ++ ) { if ( binary [ i ] === '1' ) { count ++ ; if ( count > maxCount ) { maxCount = count ; } } else { count = 0 ; } } // Return the result return maxCount ; } // Driver code let n = 14 ; console . log ( maxConsecutiveOnes ( n ));
תְפוּקָה
3