Étant donné un tableau d'entiers, la tâche consiste à diviser un tableau d'entiers en deux sous-tableaux pour rendre leurs moyennes égales si possible.
Exemples :
bordure en utilisant CSS
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 UN Approche naïve consiste à exécuter deux boucles et à trouver des sous-tableaux dont les moyennes sont égales.
Mise en œuvre:
C++// Simple C++ program to find subarrays // whose averages are equal #include
// 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.
# 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
// 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.
// 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 ?> <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>
Sortir
From (0 1) to (2 4)
Complexité temporelle : O(n2)
Espace auxiliaire : O(1)
chaîne java en booléen
Un Solution efficace est de trouver la somme des éléments du tableau. Initialisez Leftsum à zéro. Exécutez une boucle et recherchez la somme gauche en ajoutant des éléments du tableau. Pour la somme des droits, nous soustrayons la somme des feuilles de la somme totale, puis nous trouvons la somme des droits et trouvons la moyenne de la gauche et de la somme des droits en fonction de leur indice.
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.
Vous trouverez ci-dessous la mise en œuvre de l'approche ci-dessus :
C++// Efficient C++ program for // dividing array to make // average equal #include
// 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
# 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
// 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
<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>
Sortir
From (0 1) to (2 4)
Complexité temporelle : O(n)
Espace auxiliaire : O(1)
Créer un quiz