Dado un entero positivo N tal que existen dos arrays a[] y b[], cada una de las cuales contiene valores {1, 2, 3, .., N}, la tarea es encontrar el recuento de todos los pares (a[i], b[j]) tal que a[i] + b[j] es único entre todos los pares, es decir, si dos pares tienen la misma suma, solo uno se contará en el resultado.
Ejemplos:
Entrada: N = 2
Salida: 3
Explicación:
a[] = {1, 2}, b[] = {1, 2}
Los tres pares posibles son (a[0], b[0]), (a[1 ], b[0]) y (a[1], b[1]).
Par 1: 1 + 1 = 2
Par 2: 2 + 1 = 3
Par 3: 2 + 2 = 4
Entrada: N = 3
Salida: 5
a[] = {1, 2, 3}, b[] = {1 , 2, 3}
Los posibles pares con suma distinta son:
Par 1: 1 + 1 = 2
Par 2: 2 + 1 = 3
Par 3: 2 + 2 = 4
Par 4: 3 + 2 = 5
Par 5: 3 + 3 = 6
Enfoque ingenuo:
para resolver el problema mencionado anteriormente, el enfoque ingenuo es usar un Conjunto para almacenar sumas distintas de {1, 2, 3, .. N} y {1, 2, 3, .. N} usando dos bucles
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to count
// of distinct pair sum between
// two Array with values 1 to N
#include <bits/stdc++.h>
using namespace std;
// Function to find the distinct sums
int findDistinctSums(int n)
{
// Set to store distinct sums
set<int> s;
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
// Inserting every sum
s.insert(i + j);
}
}
// returning distinct sums
return s.size();
}
// Driver code
int main()
{
int N = 3;
cout << findDistinctSums(N);
return 0;
}
Java
// Java implementation to count
// of distinct pair sum between
// two Array with values 1 to N
import java.util.*;
class GFG{
// Function to find the distinct sums
static int findDistinctSums(int n)
{
// Set to store distinct sums
HashSet<Integer> s = new HashSet<>();
for(int i = 1; i <= n; i++)
{
for(int j = i; j <= n; j++)
{
// Inserting every sum
s.add(i + j);
}
}
// Returning distinct sums
return s.size();
}
// Driver code
public static void main(String[] args)
{
int N = 3;
System.out.print(findDistinctSums(N));
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 implementation to count # of distinct pair sum between # two Array with values 1 to N # Function to find the distinct sums def findDistinctSums(n): # Set to store distinct sums s = set() for i in range(1, n + 1): for j in range(i, n + 1): # Inserting every sum s.add(i + j) # Returning distinct sums return len(s) # Driver code N = 3 print(findDistinctSums(N)) # This code is contributed by divyamohan123
C#
// C# implementation to count
// of distinct pair sum between
// two Array with values 1 to N
using System;
using System.Collections.Generic;
class GFG{
// Function to find the distinct sums
static int findDistinctSums(int n)
{
// Set to store distinct sums
HashSet<int> s = new HashSet<int>();
for(int i = 1; i <= n; i++)
{
for(int j = i; j <= n; j++)
{
// Inserting every sum
s.Add(i + j);
}
}
// Returning distinct sums
return s.Count;
}
// Driver code
public static void Main(String[] args)
{
int N = 3;
Console.Write(findDistinctSums(N));
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript implementation to count
// of distinct pair sum between
// two Array with values 1 to N
// Function to find the distinct sums
function findDistinctSums(n)
{
// Set to store distinct sums
s = new Set();
for (var i = 1; i <= n; i++) {
for (var j = i; j <= n; j++) {
// Inserting every sum
s.add(i + j);
}
}
// returning distinct sums
return s.size;
}
// Driver code
var N = 3;
document.write( findDistinctSums(N));
</script>
5
Enfoque eficiente: Para optimizar el método anterior:
- Observe que la serie formada para el conteo de sumas distintas en {1, 2, 3, .., N} y {1, 2, 3, .., N} se da como 1, 3, 5, 7, …
- Por lo tanto N-ésimo término de la serie anterior = 2 * N – 1
- Por lo tanto, el recuento de la suma de pares distintos se puede calcular como 2 * N – 1
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find count
// of distinct pair sum between
// two 1 to N value Arrays
#include <bits/stdc++.h>
using namespace std;
// Function to find the distinct sums
int findDistinctSums(int N)
{
return (2 * N - 1);
}
// Driver code
int main()
{
int N = 3;
cout << findDistinctSums(N);
return 0;
}
Java
// Java implementation to find count
// of distinct pair sum between
// two 1 to N value Arrays
import java.util.*;
class GFG{
// Function to find the distinct sums
static int findDistinctSums(int N)
{
return (2 * N - 1);
}
// Driver code
public static void main(String[] args)
{
int N = 3;
System.out.print(findDistinctSums(N));
}
}
// This code is contributed by shivanisinghss2110
Python3
# Python3 implementation to find count # of distinct pair sum between # two 1 to N value Arrays # Function to find the distinct sums def findDistinctSums(N): return (2 * N - 1) # Driver code N = 3 print(findDistinctSums(N)) # This code is contributed by divyamohan123
C#
// C# implementation to find count
// of distinct pair sum between
// two 1 to N value Arrays
using System;
class GFG{
// Function to find the distinct sums
static int findDistinctSums(int N)
{
return (2 * N - 1);
}
// Driver code
public static void Main()
{
int N = 3;
Console.Write(findDistinctSums(N));
}
}
// This code is contributed by Code_Mech
Javascript
<script>
// Javascript implementation to find count
// of distinct pair sum between
// two 1 to N value Arrays
// Function to find the distinct sums
function findDistinctSums(N)
{
return (2 * N - 1);
}
let N = 3;
document.write(findDistinctSums(N));
</script>
5
Complejidad de Tiempo: O(1)
Complejidad de Espacio Auxiliar: O(1)