두 개의 누락된 숫자 찾기 | 세트 1(흥미로운 선형 시간 솔루션)
배열의 각 요소가 [1 n] 범위에 있는 n개의 고유한 정수 배열이 있다고 가정합니다. 배열에는 모든 개별 요소가 있으며 배열의 크기는 (n-2)입니다. 따라서 해당 범위의 두 숫자가 이 배열에서 누락되었습니다. 빠진 숫자 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) 추가 공간
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) 추가 공간
아이디어는 다음을 기반으로합니다. 이것 하나의 누락된 숫자를 찾는 데 널리 사용되는 솔루션입니다. 두 개의 누락된 요소가 인쇄되도록 솔루션을 확장합니다.
누락된 숫자 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부터 1까지의 자연수의 합으로 첫 번째 누락된 숫자를 찾을 수 있습니다. 평균 즉, 평균*(평균+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 기반 솔루션)
