מצא שני מספרים חסרים | סט 1 (פתרון זמן ליניארי מעניין)
נתון מערך של n מספרים שלמים ייחודיים כאשר כל אלמנט במערך נמצא בטווח [1 n]. למערך יש את כל האלמנטים הנבדלים וגודל המערך הוא (n-2). מכאן ששני מספרים מהטווח חסרים במערך זה. מצא את שני המספרים החסרים.
דוגמאות:
Input : arr[] = {1 3 5 6} Output : 2 4 Input : arr[] = {1 2 4} Output : 3 5 Input : arr[] = {1 2} Output : 3 4 שיטה 1 - O(n) מורכבות זמן ו-O(n) Extra Space
שלב 1: קח מערך בוליאני סִימָן שעוקבת אחר כל האלמנטים הקיימים במערך.
שלב 2: חזור מ-1 ל-n סימון עבור כל אלמנט אם הוא מסומן כ-true במערך הבוליאני אם לא אז פשוט הצג את האלמנט הזה.
// C++ Program to find two Missing Numbers using O(n) // extra space #include using namespace std ; // Function to find two missing numbers in range // [1 n]. This function assumes that size of array // is n-2 and all array elements are distinct void findTwoMissingNumbers ( int arr [] int n ) { // Create a boolean vector of size n+1 and // mark all present elements of arr[] in it. vector < bool > mark ( n + 1 false ); for ( int i = 0 ; i < n -2 ; i ++ ) mark [ arr [ i ]] = true ; // Print two unmarked elements cout < < 'Two Missing Numbers are n ' ; for ( int i = 1 ; i <= n ; i ++ ) if ( ! mark [ i ]) cout < < i < < ' ' ; cout < < endl ; } // Driver program to test above function int main () { int arr [] = { 1 3 5 6 }; // Range of numbers is 2 plus size of array int n = 2 + sizeof ( arr ) / sizeof ( arr [ 0 ]); findTwoMissingNumbers ( arr n ); return 0 ; }
Java // Java Program to find two Missing Numbers using O(n) // extra space import java.util.* ; class GFG { // Function to find two missing numbers in range // [1 n]. This function assumes that size of array // is n-2 and all array elements are distinct static void findTwoMissingNumbers ( int arr [] int n ) { // Create a boolean vector of size n+1 and // mark all present elements of arr[] in it. boolean [] mark = new boolean [ n + 1 ] ; for ( int i = 0 ; i < n - 2 ; i ++ ) mark [ arr [ i ]] = true ; // Print two unmarked elements System . out . println ( 'Two Missing Numbers are' ); for ( int i = 1 ; i <= n ; i ++ ) if ( ! mark [ i ] ) System . out . print ( i + ' ' ); System . out . println (); } // Driver code public static void main ( String [] args ) { int arr [] = { 1 3 5 6 }; // Range of numbers is 2 plus size of array int n = 2 + arr . length ; findTwoMissingNumbers ( arr n ); } } // This code is contributed by 29AjayKumar
Python3 # Python3 program to find two Missing Numbers using O(n) # extra space # Function to find two missing numbers in range # [1 n]. This function assumes that size of array # is n-2 and all array elements are distinct def findTwoMissingNumbers ( arr n ): # Create a boolean vector of size n+1 and # mark all present elements of arr[] in it. mark = [ False for i in range ( n + 1 )] for i in range ( 0 n - 2 1 ): mark [ arr [ i ]] = True # Print two unmarked elements print ( 'Two Missing Numbers are' ) for i in range ( 1 n + 1 1 ): if ( mark [ i ] == False ): print ( i end = ' ' ) print ( ' n ' ) # Driver program to test above function if __name__ == '__main__' : arr = [ 1 3 5 6 ] # Range of numbers is 2 plus size of array n = 2 + len ( arr ) findTwoMissingNumbers ( arr n ); # This code is contributed by # Surendra_Gangwar
C# // C# Program to find two Missing Numbers // using O(n) extra space using System ; using System.Collections.Generic ; class GFG { // Function to find two missing numbers in range // [1 n]. This function assumes that size of array // is n-2 and all array elements are distinct static void findTwoMissingNumbers ( int [] arr int n ) { // Create a boolean vector of size n+1 and // mark all present elements of arr[] in it. Boolean [] mark = new Boolean [ n + 1 ]; for ( int i = 0 ; i < n - 2 ; i ++ ) mark [ arr [ i ]] = true ; // Print two unmarked elements Console . WriteLine ( 'Two Missing Numbers are' ); for ( int i = 1 ; i <= n ; i ++ ) if ( ! mark [ i ]) Console . Write ( i + ' ' ); Console . WriteLine (); } // Driver code public static void Main ( String [] args ) { int [] arr = { 1 3 5 6 }; // Range of numbers is 2 plus size of array int n = 2 + arr . Length ; findTwoMissingNumbers ( arr n ); } } // This code contributed by Rajput-Ji
JavaScript < script > // Javascript Program to find two // Missing Numbers using O(n) extra space // Function to find two missing numbers in range // [1 n]. This function assumes that size of array // is n-2 and all array elements are distinct function findTwoMissingNumbers ( arr n ) { // Create a boolean vector of size n+1 and // mark all present elements of arr[] in it. let mark = new Array ( n + 1 ); for ( let i = 0 ; i < n - 2 ; i ++ ) mark [ arr [ i ]] = true ; // Print two unmarked elements document . write ( 'Two Missing Numbers are' + ' ' ); for ( let i = 1 ; i <= n ; i ++ ) if ( ! mark [ i ]) document . write ( i + ' ' ); document . write ( ' ' ); } let arr = [ 1 3 5 6 ]; // Range of numbers is 2 plus size of array let n = 2 + arr . length ; findTwoMissingNumbers ( arr n ); < /script>
תְפוּקָה
Two Missing Numbers are 2 4
שיטה 2 - O(n) מורכבות זמן ו-O(1) Extra Space
הרעיון מבוסס על זֶה פתרון פופולרי למציאת מספר אחד חסר. אנו מרחיבים את הפתרון כך שיודפסו שני אלמנטים חסרים.
בואו נגלה את הסכום של 2 מספרים חסרים:
arrSum => Sum of all elements in the array sum (Sum of 2 missing numbers) = (Sum of integers from 1 to n) - arrSum = ((n)*(n+1))/2 – arrSum avg (Average of 2 missing numbers) = sum / 2;
- אחד המספרים יהיה קטן או שווה ל ממוצע בעוד שהשני יהיה בהחלט גדול מ ממוצע . שני מספרים לעולם לא יכולים להיות שווים מכיוון שכל המספרים הנתונים הם נפרדים.
- נוכל למצוא את המספר החסר הראשון כסכום של מספרים טבעיים מ-1 עד ממוצע כלומר, avg*(avg+1)/2 מִינוּס סכום רכיבי המערך הקטן מ ממוצע
- נוכל למצוא את המספר החסר השני על ידי הפחתת המספר החסר הראשון מסכום המספרים החסרים
שקול דוגמה להבהרה טובה יותר
Input : 1 3 5 6 n = 6 Sum of missing integers = n*(n+1)/2 - (1+3+5+6) = 6. Average of missing integers = 6/2 = 3. Sum of array elements less than or equal to average = 1 + 3 = 4 Sum of natural numbers from 1 to avg = avg*(avg + 1)/2 = 3*4/2 = 6 First missing number = 6 - 4 = 2 Second missing number = Sum of missing integers-First missing number Second missing number = 6-2= 4
להלן יישום הרעיון לעיל.
C++ // C++ Program to find 2 Missing Numbers using O(1) // extra space #include using namespace std ; // Returns the sum of the array int getSum ( int arr [] int n ) { int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) sum += arr [ i ]; return sum ; } // Function to find two missing numbers in range // [1 n]. This function assumes that size of array // is n-2 and all array elements are distinct void findTwoMissingNumbers ( int arr [] int n ) { // Sum of 2 Missing Numbers int sum = ( n * ( n + 1 )) / 2 - getSum ( arr n -2 ); // Find average of two elements int avg = ( sum / 2 ); // Find sum of elements smaller than average (avg) // and sum of elements greater than average (avg) int sumSmallerHalf = 0 sumGreaterHalf = 0 ; for ( int i = 0 ; i < n -2 ; i ++ ) { if ( arr [ i ] <= avg ) sumSmallerHalf += arr [ i ]; else sumGreaterHalf += arr [ i ]; } cout < < 'Two Missing Numbers are n ' ; // The first (smaller) element = (sum of natural // numbers upto avg) - (sum of array elements // smaller than or equal to avg) int totalSmallerHalf = ( avg * ( avg + 1 )) / 2 ; int smallerElement = totalSmallerHalf - sumSmallerHalf ; cout < < smallerElement < < ' ' ; // The second (larger) element = (sum of both // the elements) - smaller element cout < < sum - smallerElement ; } // Driver program to test above function int main () { int arr [] = { 1 3 5 6 }; // Range of numbers is 2 plus size of array int n = 2 + sizeof ( arr ) / sizeof ( arr [ 0 ]); findTwoMissingNumbers ( arr n ); return 0 ; }
Java // Java Program to find 2 Missing // Numbers using O(1) extra space import java.io.* ; class GFG { // Returns the sum of the array static int getSum ( int arr [] int n ) { int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) sum += arr [ i ] ; return sum ; } // Function to find two missing // numbers in range [1 n]. This // function assumes that size of // array is n-2 and all array // elements are distinct static void findTwoMissingNumbers ( int arr [] int n ) { // Sum of 2 Missing Numbers int sum = ( n * ( n + 1 )) / 2 - getSum ( arr n - 2 ); // Find average of two elements int avg = ( sum / 2 ); // Find sum of elements smaller // than average (avg) and sum of // elements greater than average (avg) int sumSmallerHalf = 0 sumGreaterHalf = 0 ; for ( int i = 0 ; i < n - 2 ; i ++ ) { if ( arr [ i ] <= avg ) sumSmallerHalf += arr [ i ] ; else sumGreaterHalf += arr [ i ] ; } System . out . println ( 'Two Missing ' + 'Numbers are' ); // The first (smaller) element = // (sum of natural numbers upto // avg) - (sum of array elements // smaller than or equal to avg) int totalSmallerHalf = ( avg * ( avg + 1 )) / 2 ; System . out . println ( totalSmallerHalf - sumSmallerHalf ); // The first (smaller) element = // (sum of natural numbers from // avg+1 to n) - (sum of array // elements greater than avg) System . out . println ((( n * ( n + 1 )) / 2 - totalSmallerHalf ) - sumGreaterHalf ); } // Driver Code public static void main ( String [] args ) { int arr [] = { 1 3 5 6 }; // Range of numbers is 2 // plus size of array int n = 2 + arr . length ; findTwoMissingNumbers ( arr n ); } } // This code is contributed by aj_36
Python3 # Python Program to find 2 Missing # Numbers using O(1) extra space # Returns the sum of the array def getSum ( arr n ): sum = 0 ; for i in range ( 0 n ): sum += arr [ i ] return sum # Function to find two missing # numbers in range [1 n]. This # function assumes that size of # array is n-2 and all array # elements are distinct def findTwoMissingNumbers ( arr n ): # Sum of 2 Missing Numbers sum = (( n * ( n + 1 )) / 2 - getSum ( arr n - 2 )); #Find average of two elements avg = ( sum / 2 ); # Find sum of elements smaller # than average (avg) and sum # of elements greater than # average (avg) sumSmallerHalf = 0 sumGreaterHalf = 0 ; for i in range ( 0 n - 2 ): if ( arr [ i ] <= avg ): sumSmallerHalf += arr [ i ] else : sumGreaterHalf += arr [ i ] print ( 'Two Missing Numbers are' ) # The first (smaller) element = (sum # of natural numbers upto avg) - (sum # of array elements smaller than or # equal to avg) totalSmallerHalf = ( avg * ( avg + 1 )) / 2 print ( str ( totalSmallerHalf - sumSmallerHalf ) + ' ' ) # The first (smaller) element = (sum # of natural numbers from avg+1 to n) - # (sum of array elements greater than avg) print ( str ((( n * ( n + 1 )) / 2 - totalSmallerHalf ) - sumGreaterHalf )) # Driver Code arr = [ 1 3 5 6 ] # Range of numbers is 2 # plus size of array n = 2 + len ( arr ) findTwoMissingNumbers ( arr n ) # This code is contributed # by Yatin Gupta
C# // C# Program to find 2 Missing // Numbers using O(1) extra space using System ; class GFG { // Returns the sum of the array static int getSum ( int [] arr int n ) { int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) sum += arr [ i ]; return sum ; } // Function to find two missing // numbers in range [1 n]. This // function assumes that size of // array is n-2 and all array // elements are distinct static void findTwoMissingNumbers ( int [] arr int n ) { // Sum of 2 Missing Numbers int sum = ( n * ( n + 1 )) / 2 - getSum ( arr n - 2 ); // Find average of two elements int avg = ( sum / 2 ); // Find sum of elements smaller // than average (avg) and sum of // elements greater than average (avg) int sumSmallerHalf = 0 sumGreaterHalf = 0 ; for ( int i = 0 ; i < n - 2 ; i ++ ) { if ( arr [ i ] <= avg ) sumSmallerHalf += arr [ i ]; else sumGreaterHalf += arr [ i ]; } Console . WriteLine ( 'Two Missing ' + 'Numbers are ' ); // The first (smaller) element = // (sum of natural numbers upto // avg) - (sum of array elements // smaller than or equal to avg) int totalSmallerHalf = ( avg * ( avg + 1 )) / 2 ; Console . WriteLine ( totalSmallerHalf - sumSmallerHalf ); // The first (smaller) element = // (sum of natural numbers from // avg+1 to n) - (sum of array // elements greater than avg) Console . WriteLine ((( n * ( n + 1 )) / 2 - totalSmallerHalf ) - sumGreaterHalf ); } // Driver Code static public void Main () { int [] arr = { 1 3 5 6 }; // Range of numbers is 2 // plus size of array int n = 2 + arr . Length ; findTwoMissingNumbers ( arr n ); } } // This code is contributed by ajit
PHP // PHP Program to find 2 Missing // Numbers using O(1) extra space // Returns the sum of the array function getSum ( $arr $n ) { $sum = 0 ; for ( $i = 0 ; $i < $n ; $i ++ ) $sum += $arr [ $i ]; return $sum ; } // Function to find two missing // numbers in range [1 n]. This // function assumes that size of // array is n-2 and all array // elements are distinct function findTwoMissingNumbers ( $arr $n ) { // Sum of 2 Missing Numbers $sum = ( $n * ( $n + 1 )) / 2 - getSum ( $arr $n - 2 ); // Find average of two elements $avg = ( $sum / 2 ); // Find sum of elements smaller // than average (avg) and sum of // elements greater than average (avg) $sumSmallerHalf = 0 ; $sumGreaterHalf = 0 ; for ( $i = 0 ; $i < $n - 2 ; $i ++ ) { if ( $arr [ $i ] <= $avg ) $sumSmallerHalf += $arr [ $i ]; else $sumGreaterHalf += $arr [ $i ]; } echo 'Two Missing Numbers are n ' ; // The first (smaller) element = // (sum of natural numbers upto avg) - // (sum of array elements smaller // than or equal to avg) $totalSmallerHalf = ( $avg * ( $avg + 1 )) / 2 ; echo ( $totalSmallerHalf - $sumSmallerHalf ) ' ' ; // The first (smaller) element = // (sum of natural numbers from avg + // 1 to n) - (sum of array elements // greater than avg) echo ((( $n * ( $n + 1 )) / 2 - $totalSmallerHalf ) - $sumGreaterHalf ); } // Driver Code $arr = array ( 1 3 5 6 ); // Range of numbers is // 2 plus size of array $n = 2 + sizeof ( $arr ); findTwoMissingNumbers ( $arr $n ); // This code is contributed by aj_36 ?>
JavaScript < script > // Javascript Program to find 2 Missing // Numbers using O(1) extra space // Returns the sum of the array function getSum ( arr n ) { let sum = 0 ; for ( let i = 0 ; i < n ; i ++ ) sum += arr [ i ]; return sum ; } // Function to find two missing // numbers in range [1 n]. This // function assumes that size of // array is n-2 and all array // elements are distinct function findTwoMissingNumbers ( arr n ) { // Sum of 2 Missing Numbers let sum = ( n * ( n + 1 )) / 2 - getSum ( arr n - 2 ); // Find average of two elements let avg = ( sum / 2 ); // Find sum of elements smaller // than average (avg) and sum of // elements greater than average (avg) let sumSmallerHalf = 0 sumGreaterHalf = 0 ; for ( let i = 0 ; i < n - 2 ; i ++ ) { if ( arr [ i ] <= avg ) sumSmallerHalf += arr [ i ]; else sumGreaterHalf += arr [ i ]; } document . write ( 'Two Missing ' + 'Numbers are ' + ' ' ); // The first (smaller) element = // (sum of natural numbers upto // avg) - (sum of array elements // smaller than or equal to avg) let totalSmallerHalf = ( avg * ( avg + 1 )) / 2 ; document . write ( ( totalSmallerHalf - sumSmallerHalf ) + ' ' ); // The first (smaller) element = // (sum of natural numbers from // avg+1 to n) - (sum of array // elements greater than avg) document . write ( (( n * ( n + 1 )) / 2 - totalSmallerHalf ) - sumGreaterHalf + ' ' ); } let arr = [ 1 3 5 6 ]; // Range of numbers is 2 // plus size of array let n = 2 + arr . length ; findTwoMissingNumbers ( arr n ); < /script>
תְפוּקָה
Two Missing Numbers are 2 4
הערה: יכולות להיות בעיות הצפת בפתרון לעיל.
בסט 2 למטה נדון פתרון אחר שהוא מרחב O(n) זמן O(1) ואינו גורם לבעיות הצפה.
מצא שני מספרים חסרים | סט 2 (פתרון מבוסס XOR)
