Longest subarray having count of 1 s one more than count of 0 s | C ++ implementation to find the length of longest subarray having count of 1 ' s ▁ one ▁ more ▁ than ▁ count ▁ of ▁ 0' s ; function to find the length of longest subarray having count of 1 ' s ▁ one ▁ more ▁ than ▁ count ▁ of ▁ 0' s ; unordered_map ' um ' implemented as hash table ; traverse the given array ; consider '0' as ' - 1' ; when subarray starts form index '0' ; make an entry for ' sum ' if it is not present in ' um ' ; check if ' sum - 1' is present in ' um ' or not ; update maxLength ; required maximum length ; Driver program to test above
#include <bits/stdc++.h> NEW_LINE using namespace std ; int lenOfLongSubarr ( int arr [ ] , int n ) { unordered_map < int , int > um ; int sum = 0 , maxLen = 0 ; for ( int i = 0 ; i < n ; i ++ ) { sum += arr [ i ] == 0 ? -1 : 1 ; if ( sum == 1 ) maxLen = i + 1 ; else if ( um . find ( sum ) == um . end ( ) ) um [ sum ] = i ; if ( um . find ( sum - 1 ) != um . end ( ) ) { if ( maxLen < ( i - um [ sum - 1 ] ) ) maxLen = i - um [ sum - 1 ] ; } } return maxLen ; } int main ( ) { int arr [ ] = { 0 , 1 , 1 , 0 , 0 , 1 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << " Length ▁ = ▁ " << lenOfLongSubarr ( arr , n ) ; return 0 ; }