Given sorted float array arr[]. Check if arr[] can be rearranged such that its mean is equal to its median.
Examples:
Input: arr[] = {1.0, 3.0, 6.0, 9.0, 12.0, 32.0}
Output: Yes
Explanation: The mean of given array is (1.0 + 3.0 + 6.0 + 9.0 + 12.0 + 32.0) / 6 = 10.5.
Rearranging given array as {1.0, 3.0, 9.0, 12.0, 6.0, 32.0}, here median is (9.0 + 12.0) / 2 = 10.5Input: arr[] = {8.0, 13.0, 15.0}
Output: No
Approach: The given problem can be solved by using Binary Search and Two Pointers approach. If size of arr[] is odd that means the median is a single element that can be searched by using Binary search. If array size is even then Two pointers approach can be used because then median will be composed of two elements. Follow the steps below to solve the given problem.
- Initialize a variable say, mean to store mean of arr[].
- Check if the size of arr[] is even or odd.
- if size of arr[] is even
- Use Two Pointers approach to search two elements whose average = mean.
- Initialize two pointers as i=0, j=n-1.
- Perform two pointers approach to search for the median in arr[].
- if size of arr[] is odd
- Apply Binary Search to find if mean is present in arr[] or not.
- if size of arr[] is even
- If it is mean is found return Yes, otherwise No.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <iostream>using namespace std;// Function to return true or false if// size of array is oddbool binarySearch(float arr[], int size, float key){ int low = 0, high = size - 1, mid; while (low <= high) { // To prevent overflow mid = low + (high - low) / 2; // If element is greater than mid, then // it can only be present in right subarray if (key > arr[mid]) low = mid + 1; // If element is smaller than mid, then // it can only be present in left subarray else if (key < arr[mid]) high = mid - 1; // Else the element is present at the middle // then return 1 else return 1; } // when element is not present // in array then return 0 return 0;}// Function to return true or false// if size of array is evenbool twoPointers(float arr[], int N, float mean){ int i = 0, j = N - 1; while (i < j) { // Calculating Candidate Median float temp = (arr[i] + arr[j]) / 2; // If Candidate Median if greater // than Mean then decrement j if (temp > mean) j--; // If Candidate Median if less // than Mean then increment i else if (temp < mean) i++; // If Candidate Median if equal // to Mean then return 1 else return 1; } // when No candidate found for mean return 0;}// Function to return true if Mean// can be equal to any candidate// median otherwise return falsebool checkArray(float arr[], int N){ // Calculating Mean float sum = 0; for (int i = 0; i < N; i++) sum += arr[i]; float mean = sum / N; // If N is Odd if (N & 1) return binarySearch(arr, N, mean); // If N is even else return twoPointers(arr, N, mean);}// Driver Codeint 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;} |
Java
// Java program for the above approachimport java.io.*;public class GFG{// Function to return true or false if// size of array is oddstatic boolean binarySearch(float []arr, int size, float key){ int low = 0, high = size - 1, mid; while (low <= high) { // To prevent overflow mid = low + (high - low) / 2; // If element is greater than mid, then // it can only be present in right subarray if (key > arr[mid]) low = mid + 1; // If element is smaller than mid, then // it can only be present in left subarray else if (key < arr[mid]) high = mid - 1; // Else the element is present at the middle // then return 1 else return true; } // when element is not present // in array then return 0 return false;}// Function to return true or false// if size of array is evenstatic boolean twoPointers(float []arr, int N, float mean){ int i = 0, j = N - 1; while (i < j) { // Calculating Candidate Median float temp = (arr[i] + arr[j]) / 2; // If Candidate Median if greater // than Mean then decrement j if (temp > mean) j--; // If Candidate Median if less // than Mean then increment i else if (temp < mean) i++; // If Candidate Median if equal // to Mean then return 1 else return true; } // when No candidate found for mean return false;}// Function to return true if Mean// can be equal to any candidate// median otherwise return falsestatic boolean checkArray(float []arr, int N){ // Calculating Mean float sum = 0; for (int i = 0; i < N; i++) sum += arr[i]; float mean = sum / N; // If N is Odd if ((N & 1)!=0) return binarySearch(arr, N, mean); // If N is even else return twoPointers(arr, N, mean);}// Driver Codepublic static void main(String []args){ float []arr = { 1.0f, 3.0f, 6.0f, 9.0f, 12.0f, 32.0f }; int N = arr.length; if (checkArray(arr, N)) System.out.println("Yes"); else System.out.println("No");}}// This code is contributed by AnkThon. |
Python3
# python program for the above approach# Function to return true or false if# size of array is odddef binarySearch(arr, size, key): low = 0 high = size - 1 while (low <= high): # To prevent overflow mid = low + (high - low) // 2 # If element is greater than mid, then # it can only be present in right subarray if (key > arr[mid]): low = mid + 1 # If element is smaller than mid, then # it can only be present in left subarray elif (key < arr[mid]): high = mid - 1 # Else the element is present at the middle # then return 1 else: return 1 # when element is not present # in array then return 0 return 0# Function to return true or false# if size of array is evendef twoPointers(arr, N, mean): i = 0 j = N - 1 while (i < j): # Calculating Candidate Median temp = (arr[i] + arr[j]) / 2 # If Candidate Median if greater # than Mean then decrement j if (temp > mean): j = j - 1 # If Candidate Median if less # than Mean then increment i elif (temp < mean): i = i + 1 # If Candidate Median if equal # to Mean then return 1 else: return 1 # when No candidate found for mean return 0# Function to return true if Mean# can be equal to any candidate# median otherwise return falsedef checkArray(arr, N): # Calculating Mean sum = 0 for i in range(0, N): sum += arr[i] mean = sum / N # If N is Odd if (N & 1): return binarySearch(arr, N, mean) # If N is even else: return twoPointers(arr, N, mean)# Driver Codeif __name__ == "__main__": arr = [1.0, 3.0, 6.0, 9.0, 12.0, 32.0] N = len(arr) if (checkArray(arr, N)): print("Yes") else: print("No") # This code is contributed by rakeshsahni |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to return true or false if// size of array is oddstatic bool binarySearch(float []arr, int size, float key){ int low = 0, high = size - 1, mid; while (low <= high) { // To prevent overflow mid = low + (high - low) / 2; // If element is greater than mid, then // it can only be present in right subarray if (key > arr[mid]) low = mid + 1; // If element is smaller than mid, then // it can only be present in left subarray else if (key < arr[mid]) high = mid - 1; // Else the element is present at the middle // then return 1 else return true; } // when element is not present // in array then return 0 return false;}// Function to return true or false// if size of array is evenstatic bool twoPointers(float []arr, int N, float mean){ int i = 0, j = N - 1; while (i < j) { // Calculating Candidate Median float temp = (arr[i] + arr[j]) / 2; // If Candidate Median if greater // than Mean then decrement j if (temp > mean) j--; // If Candidate Median if less // than Mean then increment i else if (temp < mean) i++; // If Candidate Median if equal // to Mean then return 1 else return true; } // when No candidate found for mean return false;}// Function to return true if Mean// can be equal to any candidate// median otherwise return falsestatic bool checkArray(float []arr, int N){ // Calculating Mean float sum = 0; for (int i = 0; i < N; i++) sum += arr[i]; float mean = sum / N; // If N is Odd if ((N & 1)!=0) return binarySearch(arr, N, mean); // If N is even else return twoPointers(arr, N, mean);}// Driver Codepublic static void Main(){ float []arr = { 1.0f, 3.0f, 6.0f, 9.0f, 12.0f, 32.0f }; int N = arr.Length; if (checkArray(arr, N)) Console.Write("Yes"); else Console.Write("No");}}// This code is contributed by SURENDRA_GANGWAR. |
Javascript
<script> // JavaScript program for the above approach // Function to return true or false if // size of array is odd const binarySearch = (arr, size, key) => { let low = 0, high = size - 1, mid; while (low <= high) { // To prevent overflow mid = low + parseInt((high - low) / 2); // If element is greater than mid, then // it can only be present in right subarray if (key > arr[mid]) low = mid + 1; // If element is smaller than mid, then // it can only be present in left subarray else if (key < arr[mid]) high = mid - 1; // Else the element is present at the middle // then return 1 else return 1; } // when element is not present // in array then return 0 return 0; } // Function to return true or false // if size of array is even const twoPointers = (arr, N, mean) => { let i = 0, j = N - 1; while (i < j) { // Calculating Candidate Median let temp = (arr[i] + arr[j]) / 2; // If Candidate Median if greater // than Mean then decrement j if (temp > mean) j--; // If Candidate Median if less // than Mean then increment i else if (temp < mean) i++; // If Candidate Median if equal // to Mean then return 1 else return 1; } // when No candidate found for mean return 0; } // Function to return true if Mean // can be equal to any candidate // median otherwise return false const checkArray = (arr, N) => { // Calculating Mean let sum = 0; for (let i = 0; i < N; i++) sum += arr[i]; let mean = sum / N; // If N is Odd if (N & 1) return binarySearch(arr, N, mean); // If N is even else return twoPointers(arr, N, mean); } // Driver Code let arr = [1.0, 3.0, 6.0, 9.0, 12.0, 32.0]; let N = arr.length; if (checkArray(arr, N)) document.write("Yes"); else document.write("No"); // This code is contributed by rakeshsahni</script> |
Output
Yes
Time Complexity: O(N), when N is even.
O(logN), when N is odd.
Auxiliary Space: O(1).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
