Dada una array de enteros arr , la tarea es contar el número de elementos ‘A[i]’, de modo que A[i] + 1 también esté presente en la array.
Nota: si hay duplicados en la array, cuéntelos por separado.
Ejemplos:
Entrada: arr = [1, 2, 3]
Salida: 2
Explicación:
1 y 2 se cuentan porque 2 y 3 están en arr.
Entrada: arr = [1, 1, 3, 3, 5, 5, 7, 7]
Salida: 0
Enfoque 1: Solución de fuerza bruta
Para todos los elementos de la array, devuelva el recuento total después de examinar todos los elementos
- Para el elemento actual x, calcule x + 1 y busque todas las posiciones antes y después del valor actual para x + 1.
- Si encuentra x + 1, agregue 1 al conteo total
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to count of elements
// A[i] such that A[i] + 1
// is also present in the Array
#include <bits/stdc++.h>
using namespace std;
// Function to find the countElements
int countElements(int* arr, int n)
{
// Initialize count as zero
int count = 0;
// Iterate over each element
for (int i = 0; i < n; i++) {
// Store element in int x
int x = arr[i];
// Calculate x + 1
int xPlusOne = x + 1;
// Initialize found as false
bool found = false;
// Run loop to search for x + 1
// after the current element
for (int j = i + 1; j < n; j++) {
if (arr[j] == xPlusOne) {
found = true;
break;
}
}
// Run loop to search for x + 1
// before the current element
for (int k = i - 1;
!found && k >= 0; k--) {
if (arr[k] == xPlusOne) {
found = true;
break;
}
}
// if found is true, increment count
if (found == true) {
count++;
}
}
return count;
}
// Driver program
int main()
{
int arr[] = { 1, 2, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
// call countElements function on array
cout << countElements(arr, n);
return 0;
}
Java
// Java program to count of elements
// A[i] such that A[i] + 1
// is also present in the Array
import java.io.*;
import java.util.Arrays;
class GFG{
// Function to find the countElements
public static int countElements(int[] arr, int n)
{
// Initialize count as zero
int count = 0;
// Iterate over each element
for (int i = 0; i < n; i++)
{
// Store element in int x
int x = arr[i];
// Calculate x + 1
int xPlusOne = x + 1;
// Initialize found as false
boolean found = false;
// Run loop to search for x + 1
// after the current element
for (int j = i + 1; j < n; j++)
{
if (arr[j] == xPlusOne)
{
found = true;
break;
}
}
// Run loop to search for x + 1
// before the current element
for (int k = i - 1; !found && k >= 0; k--)
{
if (arr[k] == xPlusOne)
{
found = true;
break;
}
}
// If found is true, increment count
if (found == true)
{
count++;
}
}
return count;
}
// Driver code
public static void main (String[] args)
{
int arr[] = { 1, 2, 3 };
int n = arr.length;
// Call countElements function on array
System.out.println(countElements(arr, n));
}
}
//This code is contributed by shubhamsingh10
Python3
# Python3 program to count of elements # A[i] such that A[i] + 1 # is also present in the Array # Function to find the countElements def countElements(arr,n): # Initialize count as zero count = 0 # Iterate over each element for i in range(n): # Store element in int x x = arr[i] # Calculate x + 1 xPlusOne = x + 1 # Initialize found as false found = False # Run loop to search for x + 1 # after the current element for j in range(i + 1,n,1): if (arr[j] == xPlusOne): found = True break # Run loop to search for x + 1 # before the current element k = i - 1 while(found == False and k >= 0): if (arr[k] == xPlusOne): found = True break k -= 1 # if found is true, increment count if (found == True): count += 1 return count # Driver program if __name__ == '__main__': arr = [1, 2, 3] n = len(arr) # call countElements function on array print(countElements(arr, n)) # This code is contributed by Surendra_Gangwar
C#
// C# program to count of elements
// A[i] such that A[i] + 1
// is also present in the Array
using System;
class GFG{
// Function to find the countElements
static int countElements(int[] arr, int n)
{
// Initialize count as zero
int count = 0;
// Iterate over each element
for (int i = 0; i < n; i++) {
// Store element in int x
int x = arr[i];
// Calculate x + 1
int xPlusOne = x + 1;
// Initialize found as false
bool found = false;
// Run loop to search for x + 1
// after the current element
for (int j = i + 1; j < n; j++) {
if (arr[j] == xPlusOne) {
found = true;
break;
}
}
// Run loop to search for x + 1
// before the current element
for (int k = i - 1;
!found && k >= 0; k--) {
if (arr[k] == xPlusOne) {
found = true;
break;
}
}
// if found is true,
// increment count
if (found == true) {
count++;
}
}
return count;
}
// Driver program
static public void Main ()
{
int[] arr = { 1, 2, 3 };
int n = arr.Length;
// call countElements function on array
Console.WriteLine(countElements(arr, n));
}
}
// This code is contributed by shubhamsingh10
Javascript
<script>
// JavaScript program to count of elements
// A[i] such that A[i] + 1
// is also present in the Array
// Function to find the countElements
function countElements(arr, n)
{
// Initialize count as zero
let count = 0;
// Iterate over each element
for (let i = 0; i < n; i++) {
// Store element in int x
let x = arr[i];
// Calculate x + 1
let xPlusOne = x + 1;
// Initialize found as false
let found = false;
// Run loop to search for x + 1
// after the current element
for (let j = i + 1; j < n; j++)
{
if (arr[j] == xPlusOne)
{
found = true;
break;
}
}
// Run loop to search for x + 1
// before the current element
for (let k = i - 1;
!found && k >= 0; k--) {
if (arr[k] == xPlusOne) {
found = true;
break;
}
}
// if found is true, increment count
if (found == true) {
count++;
}
}
return count;
}
// Driver program
let arr = [ 1, 2, 3 ];
let n = arr.length;
// call countElements function on array
document.write(countElements(arr, n));
// This code is contributed by Surbhi Tyagi.
</script>
Producción:
2
Complejidad de tiempo : en el enfoque anterior, para un elemento dado, verificamos todos los demás elementos, por lo que la complejidad de tiempo es O (N * N) donde N es ningún elemento.
Complejidad del espacio auxiliar : en el enfoque anterior, no estamos utilizando ningún espacio adicional, por lo que la complejidad del espacio auxiliar es O(1) .
Enfoque 2: Uso del mapa
- Para todos los elementos en la array, digamos x, agregue x-1 al mapa
- Nuevamente, para todos los elementos en la array, digamos x, verifique si existe en el mapa. Si existe, incrementa el contador.
- Devuelve el recuento total después de examinar todas las claves en el mapa
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to count of elements
// A[i] such that A[i] + 1
// is also present in the Array
#include <bits/stdc++.h>
using namespace std;
// Function to find the countElements
int countElements(vector<int>& arr)
{
int size = arr.size();
// Initialize result as zero
int res = 0;
// Create map
map<int, bool> dat;
// First loop to fill the map
for (int i = 0; i < size; ++i) {
dat[arr[i] - 1] = true;
}
// Second loop to check the map
for (int i = 0; i < size; ++i) {
if (dat[arr[i]] == true) {
res++;
}
}
return res;
}
// Driver program
int main()
{
// Input Array
vector<int> arr = { 1, 3, 2, 3, 5, 0 };
// Call the countElements function
cout << countElements(arr) << endl;
return 0;
}
Java
// Java program to count of elements
// A[i] such that A[i] + 1 is
// also present in the Array
import java.util.*;
class GFG{
// Function to find the countElements
public static int countElements(int[] arr)
{
int size = arr.length;
// Initialize result as zero
int res = 0;
// Create map
Map<Integer, Boolean> dat = new HashMap<>();
// First loop to fill the map
for(int i = 0; i < size; ++i)
{
dat.put((arr[i] - 1), true);
}
// Second loop to check the map
for(int i = 0; i < size; ++i)
{
if (dat.containsKey(arr[i]) == true)
{
res++;
}
}
return res;
}
// Driver code
public static void main(String[] args)
{
// Input Array
int[] arr = { 1, 3, 2, 3, 5, 0 };
// Call the countElements function
System.out.println(countElements(arr));
}
}
// This code is contributed by shad0w1947
Python3
# Python program to count of elements
# A[i] such that A[i] + 1
# is also present in the Array
# Function to find the countElements
def countElements(arr):
size = len(arr)
# Initialize result as zero
res = 0
# Create map
dat={}
# First loop to fill the map
for i in range(size):
dat[arr[i] - 1] = True
# Second loop to check the map
for i in range(size):
if (arr[i] in dat):
res += 1
return res
# Driver program
# Input Array
arr = [1, 3, 2, 3, 5, 0]
# Call the countElements function
print(countElements(arr))
# This code is contributed by shubhamsingh10
C#
// C# program to count of elements
// A[i] such that A[i] + 1 is
// also present in the Array
using System;
using System.Collections.Generic;
class GFG{
// Function to find the countElements
public static int countElements(int[] arr)
{
int size = arr.Length;
// Initialize result as zero
int res = 0;
// Create map
Dictionary<int,
Boolean> dat = new Dictionary<int,
Boolean>();
// First loop to fill the map
for(int i = 0; i < size; ++i)
{
if(!dat.ContainsKey(arr[i] - 1))
dat.Add((arr[i] - 1), true);
}
// Second loop to check the map
for(int i = 0; i < size; ++i)
{
if (dat.ContainsKey(arr[i]) == true)
{
res++;
}
}
return res;
}
// Driver code
public static void Main(String[] args)
{
// Input Array
int[] arr = { 1, 3, 2, 3, 5, 0 };
// Call the countElements function
Console.WriteLine(countElements(arr));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// javascript program to count of elements
// A[i] such that A[i] + 1 is
// also present in the Array
// Function to find the countElements
function countElements(arr) {
var size = arr.length;
// Initialize result as zero
var res = 0;
// Create map
var dat = new Map();
// First loop to fill the map
for (i = 0; i < size; ++i) {
dat.set((arr[i] - 1), true);
}
// Second loop to check the map
for (i = 0; i < size; ++i) {
if (dat.has(arr[i]) == true) {
res++;
}
}
return res;
}
// Input Array
var arr = [ 1, 3, 2, 3, 5, 0 ];
// Call the countElements function
document.write(countElements(arr));
// This code is contributed by umadevi9616
</script>
Producción:
3
Complejidad de tiempo : en el enfoque anterior, iteramos sobre la array dos veces. Una vez para llenar el mapa y la segunda vez para verificar los elementos en el mapa, entonces la complejidad del tiempo es O (N) donde N es ningún elemento.
Complejidad del espacio auxiliar : en el enfoque anterior, estamos usando un mapa adicional que puede contener N elementos, por lo que la complejidad del espacio auxiliar es O(N) .