Daily Challenge #237 - Delete Extra Occurrences

Alice and Bob were on a holiday. Both of them took many pictures of the places they've been, and now they want to show Charlie their entire collection. However, Charlie doesn't like these gallery sessions, since the setting usually repeats. He isn't fond of seeing the Eiffel tower 40 times in a row. He tells them that he will only sit during the session if they only show the same setting at most N times. Luckily, Alice and Bob are able to encode each setting as a number. Can you help them to remove numbers such that their list contains each number only up to N times, without changing the order?

Given a list lst and a number N, create a new list that contains each number of 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], drop the next [1,2] since this would lead to 1 and 2 being in the result 3 times, and then take 3, which leads to [1,2,3,1,2,3].

Examples

delete_nth([1,1,1,1],2) # return [1,1]

delete_nth([20,37,20,21],1) # return [20,37,21]

Tests

delete_nth([1,1,3,3,7,2,2,2,2]), N= 3

delete_nth([20,37,20,21]), N = 1

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 [e-mail] with your suggestions!

Comments

[Vidit Sarkar]

Here is C++ solution,

vector<int> delete_nth(vector<int> arr, int occ){
    // stores the numbers and its corresponding count in answer vector
    unordered_map<int, int> numCount;
    // the answer vector
    vector<int> ans;

    // if count of any number is less than occ,
    // only then add it in ans
    for(int num : arr){
        if(numCount[num] < occ){
            ans.push_back(num);
            numCount[num]++;
        }
    }

    return ans;
}

[sai kiran jv]

What if given numbers are not positive ?

[Vidit Sarkar]

ans vector contains each number only up to occ times. So, occ can never be negative. If user passed a negative number as occ, then ans vector will be empty.

If given numbers are negative, still there should not be any problem. Example,

delete_nth({-1,-1,-1,-2,-3,-2,-4,-3}, 1)  => {-1,-2,-3,-4}
delete_nth({1,-2,3,-7,-2,3,-8},1)  => {1,-2,3,-7,-8}

[Mihail Malo]

Javscript

With the assumption that in a long array, most elements will be seen enough times, and we need to quickly drop them:

const delete_nth = (lst, n) => {
  const tired = new Set()
  const seen = new Map()
  return lst.filter(x => {
    if (tired.has(x)) return false
    const new_count = (seen.get(x) || 0) + 1
    if (new_count >= n) tired.add(x)
    else seen.set(x, new_count)
    return true
  })
}

Without that assumption:

const delete_nth = (lst, n) => {
  const seen = new Map()
  return lst.filter(x => {
    const count = seen.get(x) || 0
    if (count >= n) return false
    seen.set(x, count + 1)
    return true
  })
}

[peter279k]

Here is the Python solution:

def delete_nth(order,max_e):
    freq_counts = {}

    for number in order:
        if number not in freq_counts:
            freq_counts[number] = 0

    ans_order = []
    for number in order:
        freq_counts[number] += 1
        if freq_counts[number] > max_e:
            continue

        ans_order.append(number)

    return ans_order

[Matt Ellen-Tsivintzeli]

Trying to figure out a version that dosn't use a list or map to remember what's been, I've created this mess in python, that is limited to a maximum count of 999:

def nomorethancount(arr, count):
    if count < 1:
        return []

    if count > len(arr):
        return arr

    if count >= 1000:
        raise ValueError('count must be less than 1000')

    bigposnum = 0
    bignegnum = 0

    result = []

    for item in arr:
        if item < 0:
            absitem = -1 * item
            bignegnum = checkitem(absitem, item, bignegnum, count, result)
        else:
            bigposnum = checkitem(item, item, bigposnum, count, result)

    return result

def checkitem(absitem, item, bignum, count, result):
    if 1000**absitem > bignum:
        bignum += 1000**absitem
        result.append(item)
    else:
        currentcount = (bignum // 1000**absitem) % 1000
        if currentcount < count:
            result.append(item)
            bignum += 1000**absitem

    return bignum