Divida la array en dos partes con la misma suma de acuerdo con las restricciones dadas

Posted on by Rudeus Greyrat

Dada una array arr[] de N enteros, la tarea es seleccionar un entero x (que puede o no estar presente en la array) y eliminar todas sus ocurrencias de la array y dividir la array restante en dos sub no vacíos -conjuntos tales que:

  1. Los elementos del primer conjunto son estrictamente más pequeños que x .
  2. Los elementos del segundo conjunto son estrictamente mayores que x .
  3. La suma de los elementos de ambos conjuntos es igual.
      4. Si existe tal número entero, imprima Sí ; de lo contrario, imprima No.

      Ejemplos:

      Entrada: arr[] = {1, 2, 2, 5}
      Salida: Sí
      Elija x = 3, después de eliminar todas sus ocurrencias, la array se convierte en arr[] = {1, 2, 2, 5}
      {1, 2, 2} y {5} son los subconjuntos necesarios.

      Entrada: arr[] = {2, 1}
      Salida: No

      Enfoque: La idea es primero ordenar la array y para todos los números que se encuentran entre 1 y el número máximo presente en la array, aplicar la búsqueda binaria y verificar si al eliminar todas sus ocurrencias de la array, la suma de los elementos presentes en su lado izquierdo ( que son menores que él) y la suma de los elementos presentes en el lado derecho (que son mayores que él) es igual.

      A continuación se muestra la implementación del enfoque anterior:

      C++

      // C++ implementation of the approach
      #include <bits/stdc++.h>
      using namespace std;
        
      // Function that checks if the given
      // conditions are satisfied
      void IfExists(int arr[], int n)
      {
          // To store the prefix sum
          // of the array elements
          int sum[n];
        
          // Sort the array
          sort(arr, arr + n);
        
          sum[0] = arr[0];
        
          // Compute the prefix sum array
          for (int i = 1; i < n; i++)
              sum[i] = sum[i - 1] + arr[i];
        
          // Maximum element in the array
          int max = arr[n - 1];
        
          // Variable to check if there exists any number
          bool flag = false;
        
          for (int i = 1; i <= max; i++) {
        
              // Stores the index of the largest
              // number present in the array
              // smaller than i
              int findex = 0;
        
              // Stores the index of the smallest
              // number present in the array
              // greater than i
              int lindex = 0;
        
              int l = 0;
              int r = n - 1;
        
              // Find index of smallest number
              // greater than i
              while (l <= r) {
                  int m = (l + r) / 2;
        
                  if (arr[m] < i) {
                      findex = m;
                      l = m + 1;
                  }
                  else
                      r = m - 1;
              }
        
              l = 1;
              r = n;
              flag = false;
        
              // Find index of smallest number
              // greater than i
              while (l <= r) {
                  int m = (r + l) / 2;
        
                  if (arr[m] > i) {
                      lindex = m;
                      r = m - 1;
                  }
                  else
                      l = m + 1;
              }
        
              // If there exists a number
              if (sum[findex] == sum[n - 1] - sum[lindex - 1]) {
                  flag = true;
                  break;
              }
          }
        
          // If no such number exists
          // print no
          if (flag)
              cout << "Yes";
          else
              cout << "No";
      }
        
      // Driver code
      int main()
      {
          int arr[] = { 1, 2, 2, 5 };
          int n = sizeof(arr) / sizeof(int);
          IfExists(arr, n);
        
          return 0;
      }

      Java

      // Java implementation of the approach 
      import java.util.*;
        
      class GFG
      {
        
      // Function that checks if the given 
      // conditions are satisfied 
      static void IfExists(int arr[], int n) 
      { 
          // To store the prefix sum 
          // of the array elements 
          int sum[] = new int[n]; 
        
          // Sort the array 
          Arrays.sort(arr); 
        
          sum[0] = arr[0]; 
        
          // Compute the prefix sum array 
          for (int i = 1; i < n; i++) 
              sum[i] = sum[i - 1] + arr[i]; 
        
          // Maximum element in the array 
          int max = arr[n - 1]; 
        
          // Variable to check if there exists any number 
          boolean flag = false; 
        
          for (int i = 1; i <= max; i++) 
          { 
        
              // Stores the index of the largest 
              // number present in the array 
              // smaller than i 
              int findex = 0; 
        
              // Stores the index of the smallest 
              // number present in the array 
              // greater than i 
              int lindex = 0; 
        
              int l = 0; 
              int r = n - 1; 
        
              // Find index of smallest number 
              // greater than i 
              while (l <= r) 
              { 
                  int m = (l + r) / 2; 
        
                  if (arr[m] < i) 
                  { 
                      findex = m; 
                      l = m + 1; 
                  } 
                  else
                      r = m - 1; 
              } 
        
              l = 1; 
              r = n; 
              flag = false; 
        
              // Find index of smallest number 
              // greater than i 
              while (l <= r) 
              { 
                  int m = (r + l) / 2; 
        
                  if (arr[m] > i) 
                  { 
                      lindex = m; 
                      r = m - 1; 
                  } 
                  else
                      l = m + 1; 
              } 
        
              // If there exists a number 
              if (sum[findex] == sum[n - 1] - sum[lindex - 1]) 
              { 
                  flag = true; 
                  break; 
              } 
          } 
        
          // If no such number exists 
          // print no 
          if (flag) 
              System.out.println("Yes"); 
          else
              System.out.println("No"); 
      } 
        
      // Driver code 
      public static void main(String args[])
      { 
          int arr[] = { 1, 2, 2, 5 }; 
          int n = arr.length; 
          IfExists(arr, n); 
      }
      } 
        
      // This code is contributed by Arnab Kundu

      Python3

      # Python3 implementation of the approach 
        
      # Function that checks if the given 
      # conditions are satisfied 
      def IfExists(arr, n) :
        
          # To store the prefix sum 
          # of the array elements 
          sum = [0] * n; 
        
          # Sort the array 
          arr.sort(); 
        
          sum[0] = arr[0]; 
        
          # Compute the prefix sum array 
          for i in range(1, n) : 
              sum[i] = sum[i - 1] + arr[i]; 
        
          # Maximum element in the array 
          max = arr[n - 1]; 
        
          # Variable to check if there 
          # exists any number 
          flag = False; 
        
          for i in range(1, max + 1) :
        
              # Stores the index of the largest 
              # number present in the array 
              # smaller than i 
              findex = 0; 
        
              # Stores the index of the smallest 
              # number present in the array 
              # greater than i 
              lindex = 0; 
        
              l = 0; 
              r = n - 1; 
        
              # Find index of smallest number 
              # greater than i 
              while (l <= r) :
                  m = (l + r) // 2; 
        
                  if (arr[m] < i) :
                      findex = m; 
                      l = m + 1; 
                    
                  else :
                      r = m - 1; 
                
              l = 1; 
              r = n; 
              flag = False; 
        
              # Find index of smallest number 
              # greater than i 
              while (l <= r) : 
                  m = (r + l) // 2; 
        
                  if (arr[m] > i) : 
                      lindex = m; 
                      r = m - 1; 
                    
                  else :
                      l = m + 1; 
                
              # If there exists a number 
              if (sum[findex] == sum[n - 1] - 
                                 sum[lindex - 1]) : 
                  flag = True; 
                  break; 
                
          # If no such number exists 
          # print no 
          if (flag) : 
              print("Yes"); 
          else :
              print("No"); 
        
      # Driver code 
      if __name__ == "__main__" : 
        
          arr = [ 1, 2, 2, 5 ]; 
            
          n = len(arr) ;
          IfExists(arr, n); 
            
      # This code is contributed by Ryuga

      C#

      // C# implementation of the approach 
      using System;
        
      class GFG
      {
            
      // Function that checks if the given 
      // conditions are satisfied 
      static void IfExists(int[] arr, int n) 
      { 
          // To store the prefix sum 
          // of the array elements 
          int[] sum = new int[n]; 
        
          // Sort the array 
          Array.Sort(arr); 
        
          sum[0] = arr[0]; 
        
          // Compute the prefix sum array 
          for (int i = 1; i < n; i++) 
              sum[i] = sum[i - 1] + arr[i]; 
        
          // Maximum element in the array 
          int max = arr[n - 1]; 
        
          // Variable to check if there exists any number 
          bool flag = false; 
        
          for (int i = 1; i <= max; i++) 
          { 
        
              // Stores the index of the largest 
              // number present in the array 
              // smaller than i 
              int findex = 0; 
        
              // Stores the index of the smallest 
              // number present in the array 
              // greater than i 
              int lindex = 0; 
        
              int l = 0; 
              int r = n - 1; 
        
              // Find index of smallest number 
              // greater than i 
              while (l <= r) 
              { 
                  int m = (l + r) / 2; 
        
                  if (arr[m] < i) 
                  { 
                      findex = m; 
                      l = m + 1; 
                  } 
                  else
                      r = m - 1; 
              } 
        
              l = 1; 
              r = n; 
              flag = false; 
        
              // Find index of smallest number 
              // greater than i 
              while (l <= r) 
              { 
                  int m = (r + l) / 2; 
        
                  if (arr[m] > i) 
                  { 
                      lindex = m; 
                      r = m - 1; 
                  } 
                  else
                      l = m + 1; 
              } 
        
              // If there exists a number 
              if (sum[findex] == sum[n - 1] - sum[lindex - 1]) 
              { 
                  flag = true; 
                  break; 
              } 
          } 
        
          // If no such number exists 
          // print no 
          if (flag) 
              Console.WriteLine("Yes"); 
          else
              Console.WriteLine("No"); 
      } 
        
      // Driver code 
      public static void Main()
      { 
          int[] arr = { 1, 2, 2, 5 }; 
          int n = arr.Length; 
          IfExists(arr, n); 
      }
      } 
        
      // This code is contributed by Code_Mech.

      PHP

      <?php
      // PHP implementation of the approach
        
      // Function that checks if the given
      // conditions are satisfied
      function IfExists($arr, $n)
      {
          // To store the prefix $sum
          // of the array elements
          $sum = array_fill(0, $n, 0);
        
          // Sort the array
          sort($arr);
        
          $sum[0] = $arr[0];
        
          // Compute the prefix sum array
          for ($i = 1; $i < $n; $i++)
              $sum[$i] = $sum[$i - 1] + $arr[$i];
        
          // Maximum element in the array
          $max = $arr[$n - 1];
        
          // Variable to check if there exists any number
          $flag = false;
        
          for ($i = 1; $i <= $max; $i++) 
          {
        
              // Stores the index of the largest
              // number present in the array
              // smaller than i
              $findex = 0;
        
              // Stores the index of the smallest
              // number present in the array
              // greater than i
              $lindex = 0;
        
              $l = 0;
              $r = $n - 1;
        
              // Find index of smallest number
              // greater than i
              while ($l <= $r) 
              {
                  $m = ($l + $r) / 2; 
                  if ($arr[$m] < $i) 
                  {
                      $findex = $m;
                      $l = $m + 1;
                  }
                  else
                      $r = $m - 1;
              }
        
              $l = 1;
              $r = $n;
              $flag = false;
        
              // Find index of smallest number
              // greater than i
              while ($l <= $r)
              {
                  $m = ($r + $l) / 2;
        
                  if ($arr[$m] > $i) 
                  {
                      $lindex = $m;
                      $r = $m - 1;
                  }
                  else
                      $l = $m + 1;
              }
        
              // If there exists a number
              if ($sum[$findex] == $sum[$n - 1] -
                                   $sum[$lindex - 1])
              {
                  $flag = true;
                  break;
              }
          }
        
          // If no such number exists
          // print no
          if ($flag == true)
              echo "Yes";
          else
              echo "No";
      }
        
      // Driver code
      $arr = array(1, 2, 2, 5 );
      $n = sizeof($arr);
      IfExists($arr, $n);
        
      // This code is contributed by ihritik
      ?>
      Producción:

      Yes

Publicación traducida automáticamente

Artículo escrito por Sakshi_Srivastava y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *