10003. Counting Elements

Stanislav Gumeniuk included in Leetcode Leetcode-Problem

2020-04-07 440 words 3 minutes

Contents

Automatic Translation

This article has been translated automatically from Russian to English. The original is available in Russian.

Solution for problem 10003 “Counting Elements” from LeetCode.

Problem Statement

Given an integer array arr, count element x such that x + 1 is also in arr.

If there’re duplicates in arr, count them seperately.

Constraints:

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

Constraints

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

Examples

Input: arr = [1,2,3]
Output: 2
Explanation: 1 and 2 are counted because 2 and 3 exist respectively.

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

Input: arr = [1,3,2,3,5,0]
Output: 3
Explanation: 0, 1, and 2 are counted because 1, 2, and 3 are in the array.

Input: arr = [1,1,2,2]
Output: 2
Explanation: Two ones are counted because there is a 2.

Solution

Using a Map

Algorithm idea:

Create a map where the key is the number and the value is the count of occurrences in the original array.

Iterate through the original array and count all numbers.

Iterate through the map, take the current number. If the map contains a value for the current number + 1, add the count of original numbers to the result.

func countElements(arr []int) int {
    if len(arr) == 0 {
        return 0
    }

    res := 0

    up := make(map[int]int,0)
    for idx := range arr {
        up[arr[idx]]++
    }

    for jdx:= range up {
        if _, ok := up[jdx+1]; ok {
            res+=up[jdx]
        }
    }

    return res
}

Sorting with Counting

Algorithm idea:

Sort the original array

Iterate through elements, count the number of current elements (i.e., how many times the number repeats).

As soon as a new number is encountered:

if it’s greater by more than 1 - reset counters and count again
if it’s greater by exactly 1 - add the count of current elements to the final result and reset their counter.

func countElements(arr []int) int {
    if len(arr) == 0 {
        return 0
    }
    sort(arr)
    res := 0
    cur :=0
    curv:=arr[0]
    prev := 0

    for idx := range arr {
        if arr[idx]>curv && arr[idx]-curv > 1 {
            prev = 0
            cur = 0
            curv = arr[idx]

        }
        if arr[idx]>curv && arr[idx]-curv == 1 {
            prev = cur
            cur = 0
            curv = arr[idx]
        }
        if arr[idx] == curv {
            cur++
            if prev>0 {
                res+=prev
                prev = 0
            }
        }
    }

    return res
}

func sort(arr []int) {
    for idx:=range arr{
        k := idx
        for jdx:=idx;jdx>=0;jdx -- {
            if arr[jdx]>arr[k]{
                arr[jdx],arr[k] = arr[k],arr[jdx]
                k = jdx
            }
        }
    }
}