logo

חלקו את המערך לשני מערכי משנה כך שהממוצעים שלהם שווים

בהינתן מערך שלמים המשימה היא לחלק מערך שלמים לשני מערכי משנה כדי שהממוצעים שלהם יהיו שווים במידת האפשר.

דוגמאות:  

תמונת סימון
Input : arr[] = {1 5 7 2 0}; Output : (0 1) and (2 4) Subarrays arr[0..1] and arr[2..4] have same average. Input : arr[] = {4 3 5 9 11}; Output : Not possible

נשאל במיקרוסופט 



א גישה נאיבית הוא להריץ שתי לולאות ולמצוא מערכי משנה שהממוצעים שלהם שווים. 

יישום:

C++
// Simple C++ program to find subarrays // whose averages are equal #include   using namespace std; // Finding two subarrays // with equal average. void findSubarrays(int arr[] int n) {  bool found = false;  int lsum = 0;  for (int i = 0; i < n - 1; i++)  {  lsum += arr[i];  int rsum = 0;  for (int j = i + 1; j < n; j++)  rsum += arr[j];  // If averages of arr[0...i] and   // arr[i+1..n-1] are same. To avoid  // floating point problems we compare   // 'lsum*(n-i+1)' and 'rsum*(i+1)'   // instead of 'lsum/(i+1)' and   // 'rsum/(n-i+1)'  if (lsum * (n - i - 1) ==   rsum * (i + 1))  {  printf('From (%d %d) to (%d %d)n'  0 i i + 1 n - 1);  found = true;  }  }  // If no subarrays found  if (found == false)  cout << 'Subarrays not found'   << endl; } // Driver code int main() {  int arr[] = {1 5 7 2 0};  int n = sizeof(arr) / sizeof(arr[0]);  findSubarrays(arr n);  return 0; } 
Java
// Simple Java program to find subarrays // whose averages are equal public class GFG {    // Finding two subarrays  // with equal average.  static void findSubarrays(int[] arr int n)  {  boolean found = false;  int lsum = 0;    for (int i = 0; i < n - 1; i++)  {  lsum += arr[i];  int rsum = 0;    for (int j = i + 1; j < n; j++)  rsum += arr[j];    // If averages of arr[0...i] and   // arr[i+1..n-1] are same. To avoid  // floating point problems we compare   // 'lsum*(n-i+1)' and 'rsum*(i+1)'   // instead of 'lsum/(i+1)' and   // 'rsum/(n-i+1)'  if (lsum * (n - i - 1) ==   rsum * (i + 1))  {  System.out.println('From (0 ' + i   + ') to (' +(i + 1) + ' '  + (n - 1)+ ')');    found = true;  }  }    // If no subarrays found  if (found == false)  System.out.println( 'Subarrays not '  + 'found');  }    // Driver code  static public void main (String[] args)  {  int[] arr = {1 5 7 2 0};  int n = arr.length;  findSubarrays(arr n);  } } // This code is contributed by Mukul Singh. 
Python 3
# Simple Python 3 program to find subarrays # whose averages are equal # Finding two subarrays with equal average. def findSubarrays(arr n): found = False lsum = 0 for i in range(n - 1): lsum += arr[i] rsum = 0 for j in range(i + 1 n): rsum += arr[j] # If averages of arr[0...i] and  # arr[i+1..n-1] are same. To avoid # floating point problems we compare  # 'lsum*(n-i+1)' and 'rsum*(i+1)'  # instead of 'lsum/(i+1)' and  # 'rsum/(n-i+1)' if (lsum * (n - i - 1) == rsum * (i + 1)): print('From' '(' 0 i ')' 'to' '(' i + 1 n - 1 ')') found = True # If no subarrays found if (found == False): print('Subarrays not found') # Driver code if __name__ == '__main__': arr = [1 5 7 2 0] n = len(arr) findSubarrays(arr n) # This code is contributed by ita_c 
C#
// Simple C# program to find subarrays // whose averages are equal using System; public class GFG {    // Finding two subarrays  // with equal average.  static void findSubarrays(int []arr int n)  {  bool found = false;  int lsum = 0;    for (int i = 0; i < n - 1; i++)  {  lsum += arr[i];  int rsum = 0;    for (int j = i + 1; j < n; j++)  rsum += arr[j];    // If averages of arr[0...i] and   // arr[i+1..n-1] are same. To avoid  // floating point problems we compare   // 'lsum*(n-i+1)' and 'rsum*(i+1)'   // instead of 'lsum/(i+1)' and   // 'rsum/(n-i+1)'  if (lsum * (n - i - 1) ==   rsum * (i + 1))  {  Console.WriteLine('From ( 0 ' + i   + ') to(' + (i + 1) + ' '  + (n - 1) + ')');    found = true;  }  }    // If no subarrays found  if (found == false)  Console.WriteLine( 'Subarrays not '  + 'found');  }    // Driver code  static public void Main ()  {  int []arr = {1 5 7 2 0};  int n = arr.Length;  findSubarrays(arr n);  } } // This code is contributed by anuj_67. 
PHP
 // Simple PHP program to find subarrays // whose averages are equal // Finding two subarrays  // with equal average. function findSubarrays( $arr $n) { $found = false; $lsum = 0; for ( $i = 0; $i < $n - 1; $i++) { $lsum += $arr[$i]; $rsum = 0; for ( $j = $i + 1; $j < $n; $j++) $rsum += $arr[$j]; // If averages of arr[0...i] and  // arr[i+1..n-1] are same. To avoid // floating point problems we compare // 'lsum*(n-i+1)' and 'rsum*(i+1)' // instead of 'lsum/(i+1)' and 'rsum/(n-i+1)' if ($lsum * ($n - $i - 1) == $rsum * ($i + 1)) { echo 'From ( 0 ' $i' )'. ' to (' $i + 1' ' $n - 1')n'; $found = true; } } // If no subarrays found if ($found == false) echo 'Subarrays not found' ; } // Driver code $arr = array(1 5 7 2 0); $n = count($arr); findSubarrays($arr $n); // This code is contributed by vt_m ?> 
JavaScript
<script> // Simple Javascript program to find subarrays // whose averages are equal    // Finding two subarrays  // with equal average.  function findSubarrays(arrn)  {  let found = false;  let lsum = 0;    for (let i = 0; i < n - 1; i++)  {  lsum += arr[i];  let rsum = 0;    for (let j = i + 1; j < n; j++)  rsum += arr[j];    // If averages of arr[0...i] and   // arr[i+1..n-1] are same. To avoid  // floating point problems we compare   // 'lsum*(n-i+1)' and 'rsum*(i+1)'   // instead of 'lsum/(i+1)' and   // 'rsum/(n-i+1)'  if (lsum * (n - i - 1) ==   rsum * (i + 1))  {  document.write('From (0 ' + i   + ') to (' +(i + 1) + ' '  + (n - 1)+ ')');    found = true;  }  }    // If no subarrays found  if (found == false)  document.write( 'Subarrays not '  + 'found');  }    // Driver code  let arr=[1 5 7 2 0];  let n = arr.length;  findSubarrays(arr n);    // This code is contributed by avanitrachhadiya2155   </script>  

תְפוּקָה
From (0 1) to (2 4)

מורכבות זמן : O(n2
מרחב עזר: O(1)

א פתרון יעיל זה למצוא סכום של רכיבי מערך. אתחול Leftsum כאפס. הפעל לולאה ומצא את Leftsum על ידי הוספת אלמנטים של מערך. עבור הסכום הימני אנו מחסירים סכום עוז מהסכום הכולל ואז נמצא סכום זכות ונמצא ממוצע של סכום שמאל וימין כפי לפי המדד שלהם.

1) Compute sum of all array elements. Let this sum be 'sum' 2) Initialize leftsum = 0. 3) Run a loop for i=0 to n-1. a) leftsum = leftsum + arr[i] b) rightsum = sum - leftsum c) If average of left and right are same print current index as output.

להלן היישום של הגישה לעיל:

C++
// Efficient C++ program for  // dividing array to make  // average equal #include   using namespace std; void findSubarrays(int arr[] int n) {  // Find array sum  int sum = 0;  for (int i = 0; i < n; i++)  sum += arr[i];  bool found = false;  int lsum = 0;  for (int i = 0; i < n - 1; i++)  {  lsum += arr[i];  int rsum = sum - lsum;  // If averages of arr[0...i]   // and arr[i+1..n-1] are same.   // To avoid floating point problems  // we compare 'lsum*(n-i+1)'   // and 'rsum*(i+1)' instead of   // 'lsum/(i+1)' and 'rsum/(n-i+1)'  if (lsum * (n - i - 1) == rsum * (i + 1))  {  printf('From (%d %d) to (%d %d)n'  0 i i+1 n-1);  found = true;  }  }  // If no subarrays found  if (found == false)  cout << 'Subarrays not found'  << endl; } // Driver code int main() {  int arr[] = {1 5 7 2 0};  int n = sizeof(arr) / sizeof(arr[0]);  findSubarrays(arr n);  return 0; } 
Java
// Efficient Java program for  // dividing array to make  // average equal import java.util.*;   class GFG { static void findSubarrays(int arr[] int n) {  // Find array sum  int sum = 0;  for (int i = 0; i < n; i++)  sum += arr[i];  boolean found = false;  int lsum = 0;  for (int i = 0; i < n - 1; i++)  {  lsum += arr[i];  int rsum = sum - lsum;  // If averages of arr[0...i]   // and arr[i+1..n-1] are same.   // To avoid floating point problems  // we compare 'lsum*(n-i+1)'   // and 'rsum*(i+1)' instead of   // 'lsum/(i+1)' and 'rsum/(n-i+1)'  if (lsum * (n - i - 1) == rsum * (i + 1))  {  System.out.printf('From (%d %d) to (%d %d)n'  0 i i + 1 n - 1);  found = true;  }  }  // If no subarrays found  if (found == false)  System.out.println('Subarrays not found'); } // Driver code static public void main ( String []arg) {  int arr[] = {1 5 7 2 0};  int n = arr.length;  findSubarrays(arr n); } } // This code is contributed by Princi Singh 
Python3
# Efficient Python program for  # dividing array to make  # average equal def findSubarrays(arr n): # Find array sum sum = 0; for i in range(n): sum += arr[i]; found = False; lsum = 0; for i in range(n - 1): lsum += arr[i]; rsum = sum - lsum; # If averages of arr[0...i] # and arr[i + 1..n - 1] are same. # To avoid floating point problems # we compare 'lsum*(n - i + 1)' # and 'rsum*(i + 1)' instead of # 'lsum / (i + 1)' and 'rsum/(n - i + 1)' if (lsum * (n - i - 1) == rsum * (i + 1)): print('From (%d %d) to (%d %d)n'% (0 i i + 1 n - 1)); found = True; # If no subarrays found if (found == False): print('Subarrays not found'); # Driver code if __name__ == '__main__': arr = [ 1 5 7 2 0 ]; n = len(arr); findSubarrays(arr n); # This code is contributed by Rajput-Ji 
C#
// Efficient C# program for  // dividing array to make  // average equal using System;   class GFG { static void findSubarrays(int []arr int n) {  // Find array sum  int sum = 0;  for (int i = 0; i < n; i++)  sum += arr[i];  bool found = false;  int lsum = 0;  for (int i = 0; i < n - 1; i++)  {  lsum += arr[i];  int rsum = sum - lsum;  // If averages of arr[0...i]   // and arr[i+1..n-1] are same.   // To avoid floating point problems  // we compare 'lsum*(n-i+1)'   // and 'rsum*(i+1)' instead of   // 'lsum/(i+1)' and 'rsum/(n-i+1)'  if (lsum * (n - i - 1) == rsum * (i + 1))  {  Console.Write('From ({0} {1}) to ({2} {3})n'  0 i i + 1 n - 1);  found = true;  }  }  // If no subarrays found  if (found == false)  Console.WriteLine('Subarrays not found'); } // Driver code static public void Main ( String []arg) {  int []arr = {1 5 7 2 0};  int n = arr.Length;  findSubarrays(arr n); } }   // This code is contributed by Rajput-Ji 
JavaScript
<script> // Efficient Javascript program for // dividing array to make // average equal    function findSubarrays(arrn)  {  // Find array sum  let sum = 0;  for (let i = 0; i < n; i++)  sum += arr[i];  let found = false;  let lsum = 0;  for (let i = 0; i < n - 1; i++)  {  lsum += arr[i];  let rsum = sum - lsum;  // If averages of arr[0...i]  // and arr[i+1..n-1] are same.  // To avoid floating point problems  // we compare 'lsum*(n-i+1)'  // and 'rsum*(i+1)' instead of  // 'lsum/(i+1)' and 'rsum/(n-i+1)'  if (lsum * (n - i - 1) == rsum * (i + 1))  {  document.write(  'From (0 '+i+') to ('+(i+1)+' '+(n-1)+')n'  );    found = true;  }  }  // If no subarrays found  if (found == false)  document.write('Subarrays not found');  }  // Driver code  let arr=[1 5 7 2 0];  let n = arr.length;  findSubarrays(arr n);    // This code is contributed by rag2127 </script> 

תְפוּקָה
From (0 1) to (2 4)

מורכבות הזמן: O(n) 
מרחב עזר: O(1)

 

נתיב שנקבע ב-java
צור חידון