Check if given array can be rearranged such that mean is equal to median | C ++ program for the above approach ; Function to return true or false if size of array is odd ; To prevent overflow ; If element is greater than mid , then it can only be present in right subarray ; If element is smaller than mid , then it can only be present in left subarray ; Else the element is present at the middle then return 1 ; when element is not present in array then return 0 ; Function to return true or false if size of array is even ; Calculating Candidate Median ; If Candidate Median if greater than Mean then decrement j ; If Candidate Median if less than Mean then increment i ; If Candidate Median if equal to Mean then return 1 ; when No candidate found for mean ; Function to return true if Mean can be equal to any candidate median otherwise return false ; Calculating Mean ; If N is Odd ; If N is even ; Driver Code
#include <iostream> NEW_LINE using namespace std ; bool binarySearch ( float arr [ ] , int size , float key ) { int low = 0 , high = size - 1 , mid ; while ( low <= high ) { mid = low + ( high - low ) / 2 ; if ( key > arr [ mid ] ) low = mid + 1 ; else if ( key < arr [ mid ] ) high = mid - 1 ; else return 1 ; } return 0 ; } bool twoPointers ( float arr [ ] , int N , float mean ) { int i = 0 , j = N - 1 ; while ( i < j ) { float temp = ( arr [ i ] + arr [ j ] ) / 2 ; if ( temp > mean ) j -- ; else if ( temp < mean ) i ++ ; else return 1 ; } return 0 ; } bool checkArray ( float arr [ ] , int N ) { float sum = 0 ; for ( int i = 0 ; i < N ; i ++ ) sum += arr [ i ] ; float mean = sum / N ; if ( N & 1 ) return binarySearch ( arr , N , mean ) ; else return twoPointers ( arr , N , mean ) ; } int main ( ) { float arr [ ] = { 1.0 , 3.0 , 6.0 , 9.0 , 12.0 , 32.0 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; if ( checkArray ( arr , N ) ) cout << " Yes " ; else cout << " No " ; return 0 ; }