Étant donné un tableau, comptez les paires dont la valeur du produit est présente dans le tableau. 
Exemples :  
 

 Input : arr[] = {6 2 4 12 5 3}   
 Output : 3   
  All pairs whose product exist in array    
  (6  2) (2 3) (4 3)    
 Input : arr[] = {3 5 2 4 15 8}   
 Output : 2    
  
  
    
  
  
 UN     Solution simple    consiste à générer toutes les paires d'un tableau donné et à vérifier si le produit existe dans le tableau. S’il existe, incrémentez le nombre. Enfin, retournez le compte.   
 Vous trouverez ci-dessous la mise en œuvre de l'idée ci-dessus    
    
 C++   
   // C++ program to count pairs whose product exist in array   #include       using     namespace     std  ;   // Returns count of pairs whose product exists in arr[]   int     countPairs  (     int     arr  []       int     n  )   {      int     result     =     0  ;      for     (  int     i     =     0  ;     i      <     n     ;     i  ++  )      {      for     (  int     j     =     i  +  1     ;     j      <     n     ;     j  ++  )      {      int     product     =     arr  [  i  ]     *     arr  [  j  ]     ;      // find product in an array      for     (  int     k     =     0  ;     k      <     n  ;     k  ++  )      {      // if product found increment counter      if     (  arr  [  k  ]     ==     product  )      {      result  ++  ;      break  ;      }      }      }      }      // return Count of all pair whose product exist in array      return     result  ;   }   //Driver program   int     main  ()   {      int     arr  []     =     {  6       2       4       12       5       3  }     ;      int     n     =     sizeof  (  arr  )  /  sizeof  (  arr  [  0  ]);      cout      < <     countPairs  (  arr       n  );      return     0  ;   }   
  Java   
   // Java program to count pairs    // whose product exist in array   import     java.io.*  ;   class   GFG      {       // Returns count of pairs    // whose product exists in arr[]   static     int     countPairs  (  int     arr  []        int     n  )   {      int     result     =     0  ;      for     (  int     i     =     0  ;     i      <     n     ;     i  ++  )      {      for     (  int     j     =     i     +     1     ;     j      <     n     ;     j  ++  )      {      int     product     =     arr  [  i  ]     *     arr  [  j  ]     ;      // find product      // in an array      for     (  int     k     =     0  ;     k      <     n  ;     k  ++  )      {      // if product found       // increment counter      if     (  arr  [  k  ]     ==     product  )      {      result  ++  ;      break  ;      }      }      }      }      // return Count of all pair       // whose product exist in array      return     result  ;   }   // Driver Code   public     static     void     main     (  String  []     args  )      {   int     arr  []     =     {  6       2       4       12       5       3  }     ;   int     n     =     arr  .  length  ;   System  .  out  .  println  (  countPairs  (  arr       n  ));   }   }   // This code is contributed by anuj_67.   
  Python 3   
   # Python program to count pairs whose   # product exist in array   # Returns count of pairs whose    # product exists in arr[]   def   countPairs  (  arr     n  ):   result   =   0  ;   for   i   in   range   (  0     n  ):   for   j   in   range  (  i   +   1     n  ):   product   =   arr  [  i  ]   *   arr  [  j  ]   ;   # find product in an array   for   k   in   range   (  0     n  ):   # if product found increment counter   if   (  arr  [  k  ]   ==   product  ):   result   =   result   +   1  ;   break  ;   # return Count of all pair whose    # product exist in array   return   result  ;   # Driver program   arr   =   [  6     2     4     12     5     3  ]   ;   n   =   len  (  arr  );   print  (  countPairs  (  arr     n  ));   # This code is contributed   # by Shivi_Aggarwal   
  C#   
   // C# program to count pairs    // whose product exist in array    using     System  ;   class     GFG   {   // Returns count of pairs    // whose product exists in arr[]    public     static     int     countPairs  (  int  []     arr           int     n  )   {      int     result     =     0  ;      for     (  int     i     =     0  ;     i      <     n     ;     i  ++  )      {      for     (  int     j     =     i     +     1     ;     j      <     n     ;     j  ++  )      {      int     product     =     arr  [  i  ]     *     arr  [  j  ];      // find product in an array       for     (  int     k     =     0  ;     k      <     n  ;     k  ++  )      {      // if product found       // increment counter       if     (  arr  [  k  ]     ==     product  )      {      result  ++  ;      break  ;      }      }      }      }      // return Count of all pair       // whose product exist in array       return     result  ;   }   // Driver Code    public     static     void     Main  (  string  []     args  )   {      int  []     arr     =     new     int  []     {  6       2       4       12       5       3  };      int     n     =     arr  .  Length  ;      Console  .  WriteLine  (  countPairs  (  arr       n  ));   }   }   // This code is contributed by Shrikant13   
  JavaScript   
    <  script  >   // javascript program to count pairs    // whose product exist in array      // Returns count of pairs      // whose product exists in arr      function     countPairs  (  arr       n  )      {      var     result     =     0  ;      for     (  i     =     0  ;     i      <     n  ;     i  ++  )      {      for     (  j     =     i     +     1  ;     j      <     n  ;     j  ++  )      {      var     product     =     arr  [  i  ]     *     arr  [  j  ];      // find product      // in an array      for     (  k     =     0  ;     k      <     n  ;     k  ++  )      {          // if product found      // increment counter      if     (  arr  [  k  ]     ==     product  )      {      result  ++  ;      break  ;      }      }      }      }      // return Count of all pair      // whose product exist in array      return     result  ;      }      // Driver Code      var     arr     =     [     6       2       4       12       5       3     ];      var     n     =     arr  .  length  ;      document  .  write  (  countPairs  (  arr       n  ));   // This code is contributed by Rajput-Ji    <  /script>   
  PHP   
      // PHP program to count pairs   // whose product exist in array   // Returns count of pairs whose   // product exists in arr[]   function   countPairs  (  $arr     $n  )   {   $result   =   0  ;   for   (  $i   =   0  ;   $i    <   $n   ;   $i  ++  )   {   for   (  $j   =   $i   +   1   ;   $j    <   $n   ;   $j  ++  )   {   $product   =   $arr  [  $i  ]   *   $arr  [  $j  ]   ;   // find product in an array   for   (  $k   =   0  ;   $k    <   $n  ;   $k  ++  )   {   // if product found increment counter   if   (  $arr  [  $k  ]   ==   $product  )   {   $result  ++  ;   break  ;   }   }   }   }   // return Count of all pair whose    // product exist in array   return   $result  ;   }   // Driver Code   $arr   =   array  (  6     2     4     12     5     3  );   $n   =   sizeof  (  $arr  );   echo   countPairs  (  $arr     $n  );   // This code is contributed   // by Akanksha Rai   
   
    Sortir:        
    
  
 3   
 
  
    Complexité temporelle :    Sur   3   )  
  
    Espace auxiliaire :    O(1)   
 Un     Solution efficace    consiste à utiliser un « hachage » qui stocke tous les éléments du tableau. Générez toutes les paires possibles du tableau donné 'arr' et vérifiez que le produit de chaque paire est dans 'hash'. S’il existe, incrémentez le nombre. Enfin, retournez le compte.    
 Vous trouverez ci-dessous la mise en œuvre de l'idée ci-dessus    
    
 C++   
   // A hashing based C++ program to count pairs whose product   // exists in arr[]   #include       using     namespace     std  ;   // Returns count of pairs whose product exists in arr[]   int     countPairs  (  int     arr  []          int     n  )   {      int     result     =     0  ;      // Create an empty hash-set that store all array element      set   <     int     >     Hash  ;      // Insert all array element into set      for     (  int     i     =     0     ;     i      <     n  ;     i  ++  )      Hash  .  insert  (  arr  [  i  ]);      // Generate all pairs and check is exist in 'Hash' or not      for     (  int     i     =     0     ;     i      <     n  ;     i  ++  )      {      for     (  int     j     =     i     +     1  ;     j   <  n     ;     j  ++  )      {      int     product     =     arr  [  i  ]  *  arr  [  j  ];      // if product exists in set then we increment      // count by 1      if     (  Hash  .  find  (  product  )     !=     Hash  .  end  ())      result  ++  ;      }      }      // return count of pairs whose product exist in array      return     result  ;   }   // Driver program   int     main  ()   {      int     arr  []     =     {  6       2       4       12       5       3  };      int     n     =     sizeof  (  arr  )  /  sizeof  (  arr  [  0  ]);      cout      < <     countPairs  (  arr       n  )     ;      return     0  ;   }   
  Java   
   // A hashing based Java program to count pairs whose product   // exists in arr[]   import     java.util.*  ;   class   GFG   {      // Returns count of pairs whose product exists in arr[]      static     int     countPairs  (  int     arr  []       int     n  )     {      int     result     =     0  ;      // Create an empty hash-set that store all array element      HashSet   <     Integer  >     Hash     =     new     HashSet   <>  ();      // Insert all array element into set      for     (  int     i     =     0  ;     i      <     n  ;     i  ++  )      {      Hash  .  add  (  arr  [  i  ]  );      }      // Generate all pairs and check is exist in 'Hash' or not      for     (  int     i     =     0  ;     i      <     n  ;     i  ++  )      {      for     (  int     j     =     i     +     1  ;     j      <     n  ;     j  ++  )      {      int     product     =     arr  [  i  ]     *     arr  [  j  ]  ;      // if product exists in set then we increment      // count by 1      if     (  Hash  .  contains  (  product  ))      {      result  ++  ;      }      }      }      // return count of pairs whose product exist in array      return     result  ;      }      // Driver program      public     static     void     main  (  String  []     args  )         {      int     arr  []     =     {  6       2       4       12       5       3  };      int     n     =     arr  .  length  ;      System  .  out  .  println  (  countPairs  (  arr       n  ));      }   }      // This code has been contributed by 29AjayKumar   
  Python3   
   # A hashing based C++ program to count    # pairs whose product exists in arr[]   # Returns count of pairs whose product    # exists in arr[]   def   countPairs  (  arr     n  ):   result   =   0   # Create an empty hash-set that    # store all array element   Hash   =   set  ()   # Insert all array element into set   for   i   in   range  (  n  ):   Hash  .  add  (  arr  [  i  ])   # Generate all pairs and check is   # exist in 'Hash' or not   for   i   in   range  (  n  ):   for   j   in   range  (  i   +   1     n  ):   product   =   arr  [  i  ]   *   arr  [  j  ]   # if product exists in set then    # we increment count by 1   if   product   in  (  Hash  ):   result   +=   1   # return count of pairs whose    # product exist in array   return   result   # Driver Code   if   __name__   ==   '__main__'  :   arr   =   [  6     2     4     12     5     3  ]   n   =   len  (  arr  )   print  (  countPairs  (  arr     n  ))   # This code is contributed by   # Sanjit_Prasad   
  C#   
   // A hashing based C# program to count pairs whose product   // exists in arr[]   using     System  ;   using     System.Collections.Generic  ;   class     GFG   {      // Returns count of pairs whose product exists in arr[]      static     int     countPairs  (  int     []  arr       int     n  )         {      int     result     =     0  ;      // Create an empty hash-set that store all array element      HashSet   <  int  >     Hash     =     new     HashSet   <  int  >  ();      // Insert all array element into set      for     (  int     i     =     0  ;     i      <     n  ;     i  ++  )      {      Hash  .  Add  (  arr  [  i  ]);      }      // Generate all pairs and check is exist in 'Hash' or not      for     (  int     i     =     0  ;     i      <     n  ;     i  ++  )      {      for     (  int     j     =     i     +     1  ;     j      <     n  ;     j  ++  )      {      int     product     =     arr  [  i  ]     *     arr  [  j  ];      // if product exists in set then we increment      // count by 1      if     (  Hash  .  Contains  (  product  ))      {      result  ++  ;      }      }      }      // return count of pairs whose product exist in array      return     result  ;      }      // Driver code      public     static     void     Main  (  String  []     args  )         {      int     []  arr     =     {  6       2       4       12       5       3  };      int     n     =     arr  .  Length  ;      Console  .  WriteLine  (  countPairs  (  arr       n  ));      }   }   /* This code contributed by PrinciRaj1992 */   
  JavaScript   
    <  script  >   // A hashing based javascript program to count pairs whose product   // exists in arr      // Returns count of pairs whose product exists in arr      function     countPairs  (  arr          n  )     {      var     result     =     0  ;      // Create an empty hash-set that store all array element      var     Hash     =     new     Set  ();      // Insert all array element into set      for     (  i     =     0  ;     i      <     n  ;     i  ++  )     {      Hash  .  add  (  arr  [  i  ]);      }      // Generate all pairs and check is exist in 'Hash' or not      for     (  i     =     0  ;     i      <     n  ;     i  ++  )     {      for     (  j     =     i     +     1  ;     j      <     n  ;     j  ++  )     {      var     product     =     arr  [  i  ]     *     arr  [  j  ];      // if product exists in set then we increment      // count by 1      if     (  Hash  .  has  (  product  ))     {      result  ++  ;      }      }      }      // return count of pairs whose product exist in array      return     result  ;      }      // Driver program          var     arr     =     [     6       2       4       12       5       3     ];      var     n     =     arr  .  length  ;      document  .  write  (  countPairs  (  arr       n  ));   // This code contributed by Rajput-Ji    <  /script>   
   
    Sortir:        
    
  
 3   
 
  
    Complexité temporelle :    Sur   2   ) 'Sous l'hypothèse d'insertion, l'opération de recherche prend un temps O(1)'  
  
    Espace auxiliaire :    Sur)  
  
    Méthode 3 : Utilisation d’une carte non ordonnée    
 
    Approche:    
  
 1.Créez une carte vide pour stocker les éléments du tableau et leurs fréquences.   
 2. Parcourez le tableau et insérez chaque élément dans la carte avec sa fréquence.   
 3.Initialisez une variable de comptage à 0 pour suivre le nombre de paires.   
 4. Parcourez à nouveau le tableau et pour chaque élément, vérifiez s'il comporte un facteur (autre que lui-même) présent dans la carte.   
 5.Si les deux facteurs sont présents sur la carte, incrémentez le nombre de paires.   
 6.Renvoyer le nombre de paires.  
  
    Mise en œuvre:    
 C++   
   #include          using     namespace     std  ;   // Function to count pairs whose product value is present in array   int     count_Pairs  (  int     arr  []     int     n  )     {      map   <  int       int  >     mp  ;     // Create a map to store the elements of the array and their frequencies          // Initialize the map with the frequencies of the elements in the array      for     (  int     i     =     0  ;     i      <     n  ;     i  ++  )     {      mp  [  arr  [  i  ]]  ++  ;      }          int     count     =     0  ;     // Initialize the count of pairs to zero          // Traverse the array and check if arr[i] has a factor in the map      for     (  int     i     =     0  ;     i      <     n  ;     i  ++  )     {      for     (  int     j     =     1  ;     j  *  j      <=     arr  [  i  ];     j  ++  )     {      if     (  arr  [  i  ]     %     j     ==     0  )     {      int     factor1     =     j  ;      int     factor2     =     arr  [  i  ]     /     j  ;          // If both factors are present in the map then increment the count of pairs      if     (  mp  .  count  (  factor1  )     &&     mp  .  count  (  factor2  ))     {      if     (  factor1     ==     factor2     &&     mp  [  factor1  ]      <     2  )     {      continue  ;      }      count  ++  ;      }      }      }      }          // Return the count of pairs      return     count  ;   }   // Driver code   int     main  ()     {      // Example input      int     arr  []     =     {  6       2       4       12       5       3  };      int     n     =     sizeof  (  arr  )     /     sizeof  (  arr  [  0  ]);          // Count pairs whose product value is present in array      int     count     =     count_Pairs  (  arr       n  );          // Print the count      cout      < <     count      < <     endl  ;          return     0  ;   }   
  Java   
   import     java.util.HashMap  ;   import     java.util.Map  ;   public     class   Main     {      // Function to count pairs whose product value is      // present in the array      static     int     countPairs  (  int  []     arr  )      {      Map   <  Integer       Integer  >     frequencyMap      =     new     HashMap   <>  ();      // Initialize the map with the frequencies of the      // elements in the array      for     (  int     num     :     arr  )     {      frequencyMap  .  put  (      num       frequencyMap  .  getOrDefault  (  num       0  )     +     1  );      }      int     count      =     0  ;     // Initialize the count of pairs to zero      // Traverse the array and check if arr[i] has a      // factor in the map      for     (  int     num     :     arr  )     {      for     (  int     j     =     1  ;     j     *     j      <=     num  ;     j  ++  )     {      if     (  num     %     j     ==     0  )     {      int     factor1     =     j  ;      int     factor2     =     num     /     j  ;      // If both factors are present in the      // map then increment the count of      // pairs      if     (  frequencyMap  .  containsKey  (  factor1  )      &&     frequencyMap  .  containsKey  (      factor2  ))     {      if     (  factor1     ==     factor2      &&     frequencyMap  .  get  (  factor1  )       <     2  )     {      continue  ;      }      count  ++  ;      }      }      }      }      // Return the count of pairs      return     count  ;      }      public     static     void     main  (  String  []     args  )      {      // Example input      int  []     arr     =     {     6       2       4       12       5       3     };      // Count pairs whose product value is present in the      // array      int     count     =     countPairs  (  arr  );      // Print the count      System  .  out  .  println  (  count  );      }   }   
  Python   
   # Function to count pairs whose product value is present in the array   def   count_pairs  (  arr  ):   # Create a dictionary to store the elements of the array and their frequencies   mp   =   {}   # Initialize the dictionary with the frequencies of the elements in the array   for   num   in   arr  :   if   num   in   mp  :   mp  [  num  ]   +=   1   else  :   mp  [  num  ]   =   1   count   =   0   # Initialize the count of pairs to zero   # Traverse the array and check if arr[i] has a factor in the dictionary   for   num   in   arr  :   for   j   in   range  (  1     int  (  num   **   0.5  )   +   1  ):   if   num   %   j   ==   0  :   factor1   =   j   factor2   =   num   //   j   # If both factors are present in the dictionary    # then increment the count of pairs   if   factor1   in   mp   and   factor2   in   mp  :   if   factor1   ==   factor2   and   mp  [  factor1  ]    <   2  :   continue   count   +=   1   return   count   # Driver code   if   __name__   ==   '__main__'  :   # Example input   arr   =   [  6     2     4     12     5     3  ]   # Count pairs whose product value is present in the array   count   =   count_pairs  (  arr  )   # Print the count   print  (  count  )   
  C#   
   using     System  ;   using     System.Collections.Generic  ;   class     GFG     {      // Function to count pairs whose product value is      // present in array      static     int     CountPairs  (  int  []     arr       int     n  )      {      Dictionary   <  int       int  >     mp     =     new     Dictionary   <      int       int  >  ();     // Create a dictionary to store the      // elements of the array and their      // frequencies      // Initialize the dictionary with the frequencies of      // the elements in the array      for     (  int     i     =     0  ;     i      <     n  ;     i  ++  )     {      if     (  !  mp  .  ContainsKey  (  arr  [  i  ]))      mp  [  arr  [  i  ]]     =     1  ;      else      mp  [  arr  [  i  ]]  ++  ;      }      int     count      =     0  ;     // Initialize the count of pairs to zero      // Traverse the array and check if arr[i] has a      // factor in the dictionary      for     (  int     i     =     0  ;     i      <     n  ;     i  ++  )     {      for     (  int     j     =     1  ;     j     *     j      <=     arr  [  i  ];     j  ++  )     {      if     (  arr  [  i  ]     %     j     ==     0  )     {      int     factor1     =     j  ;      int     factor2     =     arr  [  i  ]     /     j  ;      // If both factors are present in the      // dictionary then increment the count      // of pairs      if     (  mp  .  ContainsKey  (  factor1  )      &&     mp  .  ContainsKey  (  factor2  ))     {      if     (  factor1     ==     factor2      &&     mp  [  factor1  ]      <     2  )     {      continue  ;      }      count  ++  ;      }      }      }      }      // Return the count of pairs      return     count  ;      }      // Driver code      static     void     Main  (  string  []     args  )      {      // Example input      int  []     arr     =     {     6       2       4       12       5       3     };      int     n     =     arr  .  Length  ;      // Count pairs whose product value is present in      // array      int     count     =     CountPairs  (  arr       n  );      // Print the count      Console  .  WriteLine  (  count  );      }   }   
  JavaScript   
   // Function to count pairs whose product value is present in the array   function     GFG  (  arr  )     {      // Create a map to store the elements of the array       // and their frequencies      const     mp     =     new     Map  ();      // Initialize the map with the frequencies of the elements       // in the array      for     (  let     i     =     0  ;     i      <     arr  .  length  ;     i  ++  )     {      if     (  !  mp  .  has  (  arr  [  i  ]))     {      mp  .  set  (  arr  [  i  ]     0  );      }      mp  .  set  (  arr  [  i  ]     mp  .  get  (  arr  [  i  ])     +     1  );      }      let     count     =     0  ;     // Initialize the count of pairs to zero      // Traverse the array and check if arr[i] has a factor in the map      for     (  let     i     =     0  ;     i      <     arr  .  length  ;     i  ++  )     {      for     (  let     j     =     1  ;     j     *     j      <=     arr  [  i  ];     j  ++  )     {      if     (  arr  [  i  ]     %     j     ===     0  )     {      const     factor1     =     j  ;      const     factor2     =     arr  [  i  ]     /     j  ;      // If both factors are present in the map      // then increment the count of pairs      if     (  mp  .  has  (  factor1  )     &&     mp  .  has  (  factor2  ))     {      if     (  factor1     ===     factor2     &&     mp  .  get  (  factor1  )      <     2  )     {      continue  ;      }      count  ++  ;      }      }      }      }      // Return the count of pairs      return     count  ;   }   // Driver code   function     main  ()     {      // Example input      const     arr     =     [  6       2       4       12       5       3  ];      // Count pairs whose product value is present in the array      const     count     =     GFG  (  arr  );      // Print the count      console  .  log  (  count  );   }   main  ();   
   
    Sortir:    
  
    3     
 
    Complexité temporelle :    O (n journal n)  
  
    Espace auxiliaire :    Sur)  
  
  
     
    
    
         Créer un quiz