Подсчитайте количество пар (i, j) таких, что arr [i] * arr [j]> arr [i] + arr [j]
Для массива arr [] неотрицательных целых чисел задача состоит в том, чтобы подсчитать пары индексов (i, j, такие, что arr [i] * arr [j]> arr [i] + arr [j], где i <j .
Примеры:
Input: arr[] = { 5, 0, 3, 1, 2 }
Output: 3Input: arr[] = { 1, 1, 1 }
Output: 0
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Наивный подход: запустите два вложенных цикла и проверьте для каждой пары, выполняется ли условие. Если условие выполняется для какой-либо пары, обновите count = count + 1 и напечатайте счет в конце.
Ниже представлена реализация описанного выше подхода:
C ++
// C++ program to count pairs (i, j)// such that arr[i] * arr[j] > arr[i] + arr[j]#include <bits/stdc++.h>using namespace std; // Function to return the count of pairs// such that arr[i] * arr[j] > arr[i] + arr[j]long countPairs( int arr[], int n){ long count = 0; for ( int i = 0; i < n - 1; i++) { for ( int j = i + 1; j < n; j++) { // If condition is satisfied if (arr[i] * arr[j] > arr[i] + arr[j]) count++; } } count; return} // Driver codeint main(){ int arr[] = { 5, 0, 3, 1, 2 }; int n = sizeof (arr) / sizeof (arr[0]); cout << countPairs(arr, n); return 0;} |
Джава
// Java program to count pairs (i, j)// such that arr[i] * arr[j] > arr[i] + arr[j]import java.util.*; class solution{ // Function to return the count of pairs// such that arr[i] * arr[j] > arr[i] + arr[j]static long countPairs( int arr[], int n){ long count = 0 ; for ( int i = 0 ; i < n - 1 ; i++) { for ( int j = i + 1 ; j < n; j++) { // If condition is satisfied if (arr[i] * arr[j] > arr[i] + arr[j]) count++; } } count; return} // Driver codepublic static void main(String args[]){ int arr[] = { 5 , 0 , 3 , 1 , 2 }; int n = arr.length; System.out.println(countPairs(arr, n)); }} // This code is contributed by// Surendra_Gangwar |
Python3
# Python3 program to count pairs(i,j)# such that arr[i]*arr[j]>arr[i]+arr[j]import math as mt # function to return the count of pairs# such that arr[i]*arr[j]>arr[i]+arr[j]def countPairs(arr, n): count = 0 for i in range (n): for j in range (i + 1 , n): # if condition is satisified if arr[i] * arr[j] > arr[i] + arr[j]: count + = 1 count return # Driver codearr = [ 5 , 0 , 3 , 1 , 2 ]n = len (arr) print (countPairs(arr, n)) # This code is contributed# by Mohit Kumar 29 |
C #
// C# program to count pairs (i, j)// such that arr[i] * arr[j] > arr[i] + arr[j] using System; public class GFG{ // Function to return the count of pairs// such that arr[i] * arr[j] > arr[i] + arr[j]static long countPairs( int []arr, int n){ long count = 0; for ( int i = 0; i < n - 1; i++) { for ( int j = i + 1; j < n; j++) { // If condition is satisfied if (arr[i] * arr[j] > arr[i] + arr[j]) count++; } } count; return} // Driver code static public void Main (){ int []arr = { 5, 0, 3, 1, 2 }; int n = arr.Length; Console.WriteLine (countPairs(arr, n)); }} |
PHP
<?php// PHP program to count pairs (i, j)// such that arr[i] * arr[j] > arr[i] + arr[j] // Function to return the count of pairs// such that arr[i] * arr[j] > arr[i] + arr[j]function countPairs( $arr , $n ){ $count = 0; for ( $i = 0; $i < $n - 1; $i ++) { for ( $j = $i + 1; $j < $n ; $j ++) { // If condition is satisfied if ( $arr [ $i ] * $arr [ $j ] > $arr [ $i ] + $arr [ $j ]) $count ++; } } return $count ;} // Driver code$arr = array ( 5, 0, 3, 1, 2 );$n = sizeof( $arr ) ; echo countPairs( $arr , $n ); // This code is contributed by Ryuga?> |
3
Эффективный подход: рассмотрим следующие случаи:
1) arr[i] = 0 or arr[i] = 1 and arr[j] = any element
In this case, arr[j] * arr[i] will always be less than arr[i] + arr[j].
Hence we can discard all pairs which have one element either 0 or 1.2) arr[i] = 2 and arr[j] <= 2
In this case, arr[j] * arr[i] will always be less than or equal to arr[i] + arr[j].
Hence again we can discard all such pairs.3) arr[i] = 2 and arr[j] > 2
This case will produce valid pairs. If count_2 is the count of ‘2’s and count_others
is the count of elements greater than 2,
then number of pairs will be count_2 * count_others.4) arr[i] > 2 and arr[j] > 2
This case will also produce valid pairs. Let count_others be the number of elements
greater than 2, then every two elements among these count_others elements
will form a valid pair. Hence the number of pairs will beTherefore, total count = (count_2 * count_others) + (count_others * (count_others – 1)) / 2.
Ниже представлена реализация описанного выше подхода:
C ++
// C++ program to count pairs (i, j)// such that arr[i] * arr[j] > arr[i] + arr[j]#include <bits/stdc++.h>using namespace std; // Function to return the count of pairs// such that arr[i] * arr[j] > arr[i] + arr[j]long countPairs( const int * arr, int n){ int count_2 = 0, count_others = 0; for ( int i = 0; i < n; i++) { if (arr[i] == 2) count_2++; else if (arr[i] > 2) count_others++; } long ans = 1L * count_2 * count_others + (1L * count_others * (count_others - 1)) / 2; return ans;} // Driver codeint main(){ int arr[] = { 5, 0, 3, 1, 2 }; int n = sizeof (arr) / sizeof (arr[0]); cout << countPairs(arr, n); return 0;} |
Джава
// Java program to count pairs (i, j)// such that arr[i] * arr[j] > arr[i] + arr[j] class GFG{ // Function to return the count of pairs // such that arr[i] * arr[j] > arr[i] + arr[j] static long countPairs( int [] arr, int n) { int count_2 = 0 , count_others = 0 ; for ( int i = 0 ; i < n; i++) { if (arr[i] == 2 ) { count_2++; } else if (arr[i] > 2 ) { count_others++; } } long ans = 1L * count_2 * count_others + (1L * count_others * (count_others - 1 )) / 2 ; return ans; } // Driver code public static void main(String[] args) { int arr[] = { 5 , 0 , 3 , 1 , 2 }; int n = arr.length; System.out.println(countPairs(arr, n)); }} // This code is contributed by// 29AjayKumar |
Python3
# Python3 program to count pairs(i,j)# such that arr[i]*arr[j]>arr[i]+arr[j]import math as mt # function to return the count of pairs# such that arr[i]*arr[j]>arr[i]+arr[j]def countPairs(arr, n): count_2, count_others = 0 , 0 for i in range (n): if arr[i] = = 2 : count_2 + = 1 elif arr[i] > 2 : count_others + = 1 ans = (count_2 * count_others + (count_others * (count_others - 1 )) / / 2 ) return ans # Driver codearr = [ 5 , 0 , 3 , 1 , 2 ]n = len (arr) print (countPairs(arr, n)) # This code is contributed# by Mohit Kumar |
C #
// C# program to count pairs (i, j) such// that arr[i] * arr[j] > arr[i] + arr[j]using System; class GFG{ // Function to return the count of pairs // such that arr[i] * arr[j] > arr[i] + arr[j] static long countPairs( int [] arr, int n) { int count_2 = 0, count_others = 0; for ( int i = 0; i < n; i++) { if (arr[i] == 2) { count_2++; } else if (arr[i] > 2) { count_others++; } } long ans = 1L * count_2 * count_others + (1L * count_others * (count_others - 1)) / 2; return ans; } // Driver code public static void Main() { int [] arr = {5, 0, 3, 1, 2}; int n = arr.Length; Console.WriteLine(countPairs(arr, n)); }} // This code is contributed by// Mukul Singh |
PHP
<?php// PHP program to count pairs (i, j) such// that arr[i] * arr[j] > arr[i] + arr[j] // Function to return the count of pairs// such that arr[i] * arr[j] > arr[i] + arr[j]function countPairs( $arr , $n ){ $count_2 = 0; $count_others = 0; for ( $i = 0; $i < $n ; $i ++) { if ( $arr [ $i ] == 2) $count_2 ++; else if ( $arr [ $i ] > 2) $count_others ++; } $ans = $count_2 * $count_others + ( $count_others * ( $count_others - 1)) / 2; return $ans ;} // Driver code$arr = array ( 5, 0, 3, 1, 2 );$n = sizeof( $arr );echo countPairs( $arr , $n ); // This code is contributed// by Akanksha Rai?> |
3
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.