# 1426. Counting Elements

## Description

Given an integer array arr, count how many elements x there are, such that x + 1 is also in arr. If there are duplicates in arr, count them separately.

Example 1:

Input: arr = [1,2,3]
Output: 2
Explanation: 1 and 2 are counted cause 2 and 3 are in arr.


Example 2:

Input: arr = [1,1,3,3,5,5,7,7]
Output: 0
Explanation: No numbers are counted, cause there is no 2, 4, 6, or 8 in arr.


Constraints:

• 1 <= arr.length <= 1000
• 0 <= arr[i] <= 1000

## Solutions

Solution 1: Counting

We can use a hash table or array $cnt$ to record the frequency of each number in the array $arr$. Then, we traverse each number $x$ in $cnt$. If $x+1$ also exists in $cnt$, we add $cnt[x]$ to the answer.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array $arr$.

• class Solution {
public int countElements(int[] arr) {
int[] cnt = new int[1001];
for (int x : arr) {
++cnt[x];
}
int ans = 0;
for (int x = 0; x < 1000; ++x) {
if (cnt[x + 1] > 0) {
ans += cnt[x];
}
}
return ans;
}
}

• class Solution {
public:
int countElements(vector<int>& arr) {
int cnt[1001]{};
for (int x : arr) {
++cnt[x];
}
int ans = 0;
for (int x = 0; x < 1000; ++x) {
if (cnt[x + 1]) {
ans += cnt[x];
}
}
return ans;
}
};

• class Solution:
def countElements(self, arr: List[int]) -> int:
cnt = Counter(arr)
return sum(v for x, v in cnt.items() if cnt[x + 1])


• func countElements(arr []int) (ans int) {
mx := slices.Max(arr)
cnt := make([]int, mx+1)
for _, x := range arr {
cnt[x]++
}
for x := 0; x < mx; x++ {
if cnt[x+1] > 0 {
ans += cnt[x]
}
}
return
}

• function countElements(arr: number[]): number {
const mx = Math.max(...arr);
const cnt = Array(mx + 1).fill(0);
for (const x of arr) {
++cnt[x];
}
let ans = 0;
for (let i = 0; i < mx; ++i) {
if (cnt[i + 1] > 0) {
ans += cnt[i];
}
}
return ans;
}


• /**
* @param {number[]} arr
* @return {number}
*/
var countElements = function (arr) {
const mx = Math.max(...arr);
const cnt = Array(mx + 1).fill(0);
for (const x of arr) {
++cnt[x];
}
let ans = 0;
for (let i = 0; i < mx; ++i) {
if (cnt[i + 1] > 0) {
ans += cnt[i];
}
}
return ans;
};


• class Solution {
/**
* @param Integer[] $arr * @return Integer */ function countElements($arr) {
$cnt = array_count_values($arr);
$ans = 0; foreach ($cnt as $x =>$v) {
if (isset($cnt[$x + 1])) {
$ans +=$v;
}
}
return \$ans;
}
}


• use std::collections::HashMap;

impl Solution {
pub fn count_elements(arr: Vec<i32>) -> i32 {
let mut cnt = HashMap::new();
for &num in &arr {
*cnt.entry(num).or_insert(0) += 1;
}
cnt.iter()
.filter(|(&x, _)| cnt.contains_key(&(x + 1)))
.map(|(_, &v)| v)
.sum()
}
}