Solution for p45 variant

#1

There’s a problem in the array chapter that says if an element x in the array appears m times modify A so that it appears min(2, m) times. I’m having trouble thinking of a way to do it in O(n) space and I’m wondering if someone ahs solved this.

It may not be page 45 I’m not in front of my book.

0 Likes

#2

Please provide the problem number and title, and the version of EPI you’re using.

0 Likes

#3

EPI in Python. p46 (arrays chapter) second variant. “Write a program which takes as input a sorted array A of integers and a positive integer m and updates A so that if x appears m times in a it appears min(2, m) times in the new array. It must be done in O(n) space and O(1) time.”

0 Likes

#4

Please provide the title of the problem that it’s a variant of, because variants aren’t listed in table of contents, and page number doesn’t help because problems move around based on version (python/java…) and print edition.

0 Likes

#5

Delete duplicates from a sorted array.

0 Likes

#6

Either you made a mistake while typing the variant description, or the EPI edition you have has a typo. My version of EPI (Java page 70) does not say “It must be done in O(n) space and O(1) time.” It says the update to A should be done in one pass and no additional storage should be allocated. That’s O(1) space and O(n) time.

0 Likes

#7

Lol my bad, I made a typo. O(n) time and O(1) space.

0 Likes

#8

I haven’t solved it. But after looking at the problem, I believe I know how to. What’s your question?

0 Likes

#9

I’m wondering that the solution is. I’m tried counting the number of times an element appeared by using the difference between i and the vacant index but the output is wrong. I’ve been on this for 2 days and I just need to see a solution to internalize it.

0 Likes

#10

Most people don’t do the variants.

If you’re finding them difficult, and find yourself needing to see solutions, I advise you switch to first completing all the problems that do have solutions provided in the book.

That’ll strengthen your problem solving skills to the point where you’ll be in a better position to tackle the variants without help. If you feel you must look at the solutions, I have ones to many variants here and here.

I’ll be be adding a solution for the problem you asked about within the next week or so.

0 Likes

#11

I realize it’s bad that I don’t see the variant solutions, but that’s why I’m going through this book. I appreciate you writing up a solution.

0 Likes

#12

There’s nothing bad about not knowing. What matters is what you do next, once you know that you don’t know.

0 Likes

#13

@doremi Here you go: solution here, tests here.

0 Likes

#14

Do you mind giving the psuedocode? I’m having trouble reading Kotlin. I want to understand how to think about these problems

0 Likes

#15

@doremi sorry, i can’t take the time to do that for you. i need to move on to the next problem. try running it through a decompiler. https://stackoverflow.com/a/34960466/369722

0 Likes

#16

I mean it’s just a short paragraph on the intuition of what’s being done. I’m not ask for a line-by-line walkthrough.

0 Likes

#17

Here’s my python solution in case anyone is looking up this question. Works for m >= 1 but unfortunately not for m = 0. I like it though since it looks similar to the original algo.

def fcn(arr, m):
    vacant, l, n = 1, 1, len(arr)
    # vacant represents the index at which to move current array element
    # l is how many times the number of interest appears. l set to 1 because
    # first element appears at least once.
    # number of interest is number immediately before vacant
    for i in range(1, n):
        if arr[i] == arr[vacant - 1] and l < min(2, m):
            arr[vacant] = arr[i]
            vacant, l = vacant + 1, l + 1
            # ex) [2, 2, 3 ...] where vacant = 1
            # 2 is the number of interest and appears once (so far). Because l < min(2, m), 
            # we increment l by 1, and increment the vacant position by 1 because need
            # the number at arr[vacant - 1] to appear at least l times. 
        elif not arr[i] == arr[vacant - 1]:
            arr[vacant] = arr[i]
            l, vacant = 1, vacant + 1
            # when we hit this conditional, it means that we're operating on a new
            # number of interest, thus we reset l to 1 because the element at arr[i]
            # appears once (so far), and subsequently we move it back to vacant.
        # outside of the conditional, we don't want to increment vacant if we run into
        # the number of interest more than min(2, m) times. ex) [2, 2, 2, 2, 2, ....]
        # we only want the number of interest - 2 - to appear min(m, 2) times, so the vacant
        # position is the one right after 2 appears min(m, 2) times.

    return arr[:vacant][:]

    
0 Likes