dev.to staff

Posted on Mar 19, 2020

Daily Challenge #208 - Delete Occurrences of an Element

#challenge

Given a list lst and a number N, create a new list that contains each number in lst at most N times without reordering.

For example if N = 2, and the input is [1,2,3,1,2,1,2,3], you take [1,2,3,1,2], skip the next 1 and 2 because this would lead to those numbers being in the result more than N times. Finally, take 3, which leads to [1,2,3,1,2,3].

deleteNth([1,1,1,1],2) // return [1,1]

deleteNth([20,37,20,21],1) // return [20,37,21]

Tests

deleteNth([20,37,20,21], 1)
deleteNth([1,1,3,3,7,2,2,2,2], 3)

Good luck!

This challenge comes from JustyFY on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

Top comments (12)

David • Mar 19 '20

Just joined the community! I guess reducer is overkill here but still 🤷

let elements = {};

function deleteNth(lst, n) {
  const reducer = (acc, curVal) => {
    if (elements[curVal]) {
      elements[curVal] += 1;
      if(elements[curVal] <= n) {
        acc.push(curVal)
      }
    } else {
      elements[curVal] = 1;
      acc.push(curVal);
    }
    return acc
  }

  const newlst = lst.reduce(reducer, [])




  console.log(newlst)
}

Avalander • Mar 19 '20

Hmm... I wonder what happens if deleteNth is invoked more than once :P

David • Mar 19 '20

haha, you re right! Missed that one. Moved the obj initialisation inside the func.

Amin • Mar 19 '20 • Edited

JavaScript

function deleteNth([item, ...items], maximum, occurrences = {}) {
    if (item === undefined) {
        return [];
    }

    if (!occurrences[item]) {
        occurrences[item] = 1;
    } else {
        occurrences[item]++;
    }

    if (occurrences[item] > maximum) {
        return deleteNth(items, maximum, occurrences);
    }

    return [item, ...deleteNth(items, maximum, occurrences)];
}

Avalander • Mar 19 '20

Scala

  def deleteNth[T] (xs: Seq[T], n: Int): Seq[T] = {
    val count = Map[T, Int]() withDefaultValue 0
    val acc = List[T]()
    val (_, result) = xs.foldLeft((count, acc)) {
      case ((count, prev), x) =>
        if (count(x) >= n) (count, prev)
        else {
          val items = count(x)
          val newCount = count.updated(x, items + 1)
          (newCount, x :: prev)
        }
    }
    result.reverse
  }

Matt Ellen-Tsivintzeli • Mar 20 '20

Javascript Map:

function onlyN(arr, N)
{
  let countMap = new Map();
  return arr.filter(el =>
  {
    if(countMap.has(el))
    {
      countMap.set(el, countMap.get(el)+1)
    }
    else
    {
      countMap.set(el, 1);
    }
    return countMap.get(el) <= N;
  });
}

Valts Liepiņš • Mar 19 '20

Haskell:

import Data.List (foldl')
import qualified Data.IntMap.Strict as Map

deleteNth :: Int -> [Int] -> [Int]
deleteNth n = reverse . fst . foldl' fn ([], Map.empty)
  where
    fn (out, set) i =
      case Map.lookup i set of
        Nothing       -> (i:out, Map.insert i 1 set)
        Just x
          | x < n     -> (i:out, Map.insert i (x+1) set)
          | otherwise -> (out, set)

Cameron Desautels • Mar 19 '20 • Edited

Clojure

(defn delete-nth [xs n]
  (-> (reduce (fn [[cnts xs'] x]
                [(update cnts x (fnil inc 0))
                 (cond-> xs' (< (cnts x 0) n) (conj x))])
              [{} []] xs)
      (second)))

recur-based version, for comparison's sake:

(defn delete-nth' [xs n]
  (loop [cnts {}, xs' [], [x & rst] xs]
    (if x
      (recur (update cnts x (fnil inc 0))
             (cond-> xs' (< (cnts x 0) n) (conj x))
             rst)
      xs')))

edh_developer • Mar 21 '20

Java

        static List<Integer> deleteNth(List<Integer> vals, int n) {
                Map<Integer,Integer> numOfInstances = new HashMap<Integer,Integer>();
                List<Integer> updatedList = new ArrayList<Integer>();

                for (Integer i : vals) {
                        Integer currentTotal = numOfInstances.get(i);
                        if (currentTotal == null)
                                currentTotal = 1;
                        else
                                currentTotal += 1;

                        numOfInstances.put(i, currentTotal);

                        if (currentTotal <= n)
                                updatedList.add(i);
                }

                return updatedList;
        }

Sabin Pandelovitch • Mar 19 '20

JS solution

const deleteNth = (arr, c) => arr.reduce((a, v) => a.filter(e => e === v).length < c ? [...a, v] : a, []);

Nghia Nguyen • Mar 20 '20 • Edited

C++

std::vector deleteNth(const std::vector& lst, int n)
{
std::vector out;
std::map count;
for(auto i : lst)
{
if(count[i] < n)
{
count[i] = count[i] + 1;
out.push_pack(i);
}
}
return out;
}

Empereol • Mar 19 '20

TypeScript

function deleteNth(lst: number[], n: number): number[] {
  return lst.reduce(
    (arr, cur) => (arr.filter(i => i === cur).length < n ? [...arr, cur] : arr),
    []
  );
}

View full discussion (12 comments)