We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Modify The Sequence
  5. Discussions

Modify The Sequence

  • mariLiis
     + 0 comments

    Could someone give me a hint or a useful midrange test case? All the small ones pass and big ones are too big to debug. At each step I'm considering the possibilities that either current number in sequence is changed or last one is changed or nothing is changed. I'm going to add my code, would appreciate if someone would be kind enough to provide a test case that is not too big where my code fails.

    public static int modifySequence(List<Integer> arr) {
        int changedValue = 1;
        int noChange = arr.get(0);
        // count if this changes
        int cc = changedValue == noChange ? 0 : 1;
        // count if current does not change
        int cnc = 0;
        for (int i = 1; i < arr.size(); i++) {
            if (arr.get(i) <= noChange) {
                // Can work if previous value changed
                if (arr.get(i) > changedValue) {
                    changedValue = noChange + 1;
                    cc = cnc + 1;
                    noChange = arr.get(i);
                    cnc = cc;
                // This value definitely needs to change
                } else {
                    changedValue = (cc < cnc ? changedValue : noChange) + 1;
                    cc = Math.min(cc, cnc) + 1;
                    noChange = changedValue;
                    cnc = cc;
                }
            // No need to change
            } else {
                changedValue = (cc < cnc ? changedValue : noChange) + 1;
                noChange = arr.get(i);
                cc = Math.min(cc, cnc) + (changedValue == noChange ? 0:1);
            }
        }
        return Math.min(cc,cnc);
    }