Java array and for loop causing wrong output

Question

The requirements are to check for duplicate items in the array and delete it, the remaining items in the array must then shift to the left.

I wrote this:

public class TestRepeat {

public static int deleteRepeats(char[] ch) {

    int count = 0;
    for (int x = 0; x < ch.length; x++) {
        for (int y = x + 1; y < ch.length; y++) {
            if (ch[x] == ch[y]) {
                for (int k = y; k < ch.length - 1; k++) {//shifts the array to the right if its a duplicate
                    ch[k] = ch[k + 1];
                }
                ch[ch.length - 1] = ' ';//replaces the last array with a blank
            }
        }
    }
    for (int q = 0; q < ch.length; q++) {
        if (ch[q] == ' ') {
            count++;
        }
    }
    return count;//returns the number of deleted items
}

public static void main(String[] args) {
    char[] ch = {'k', 'a', 'm', 'o', 'k', 'm', 'y', 'm', 'k', 'k', 'x', 'm', 'm', 'o'};
    System.out.print("The original array is: ");
    System.out.println(ch);
    System.out.println("Number of deleted characters: " + deleteRepeats(ch));
    System.out.print("The new array is: ");
    System.out.println(ch);
}

}

its supposed to return:

The original array is: kamokmymkkxmmo

Number of deleted characters: 8

The new array is: kamoyx

but instead is returning:

The original array is: kamokmymkkxmmo

Number of deleted characters: 6

The new array is: kamoykxm

What is causing the problem and how can I fix it?

stackoverflow is not correct portal for this, please ask this on : http://codereview.stackexchange.com/ — NoobEditor, Aug 29 '14 at 04:45
@NoobEditor why is this not the correct portal? He has a programming error which he does not know how to fix. — Scary Wombat, Aug 29 '14 at 04:48

Mshnik · Answer 1 · 2014-08-29T04:53:51.363

I found two errors, one of which was causing your problem and the other was a corollary. First, you can't use a for loop for the inner loop because sometimes you are modifying the array you are looping over. Therefore on some iterations you are implicitly incrementing y twice: once by actually incrementing y, and again when you shift the part of array to the left. Thus, you should only actually be incrementing y when you don't perform a change on the array, and leave y where it is when you do delete an element. Second, you have to make sure you don't try to delete ' ', because it will cause infinite recursion in the while loop version. The errors are fixed below:

public class TestRepeat {

/** Deletes index index in arr. Elements in (index, arr.length) are shifted to the left,
    And a ' ' is put at the end of arr 
    Precondition: index >= 0, index < arr.length */
private static void deleteAndShift(char[] arr, int index){
    for(int i = index; i < arr.length - 1; i++){
        arr[i] = arr[i+1];
    }
    arr[arr.length - 1] = ' ';
}

public static int deleteRepeats(char[] ch) {

    int count = 0;
    for (int x = 0; x < ch.length; x++) {
        int y = x+1;
        while(y < ch.length){
            //Delete index y. Note that this 'implicitly' increments y by shifting ch.
            if (ch[x] != ' ' && ch[x] == ch[y]) {
               deleteAndShift(ch, y);
            }
            //Only increment y if an element wasn't deleted
            else{
              y++;
            }
        }
    }
    for (int q = 0; q < ch.length; q++) {
        if (ch[q] == ' ') {
            count++;
        }
    }
    return count;//returns the number of deleted items
}

public static void main(String[] args) {
    char[] ch = {'k', 'a', 'm', 'o', 'k', 'm', 'y', 'm', 'k', 'k', 'x', 'm', 'm', 'o'};
    System.out.print("The original array is: ");
    System.out.println(ch);
    System.out.println("Number of deleted characters: " + deleteRepeats(ch));
    System.out.print("The new array is: ");
    System.out.println(ch);
}

}

This code has your desired output of deleting 8 characters in the sample input.

score 0 · Answer 2 · answered Aug 29 '14 at 04:57

0

Replace the if condition block if (ch[x] == ch[y]) { with,

if (ch[x] != ' ' && ch[x] == ch[y]) {                   
   for (int k = y; k < ch.length - 1; k++) {//shifts the array to the right if its a duplicate                      
       ch[k] = ch[k + 1];
   }                    
   ch[ch.length - 1] = ' ';//replaces the last array with a blank
   y--;
}

answered Aug 29 '14 at 04:57

Wundwin Born

3,467
19
37

Altering the value of a for-loop index variable within the for loop isn't very good practice.. – Mshnik Aug 29 '14 at 05:01
@Mshnik can alter if the control is fine, `y++` or `y--` in the loop. – Wundwin Born Aug 29 '14 at 05:11

score 0 · Answer 3 · answered Aug 29 '14 at 05:01

0

After you shift them to the left, do a y--; This will help taking care of consecutive repeated elements

answered Aug 29 '14 at 05:01

venkatesh

1

score 0 · Answer 4 · answered Aug 29 '14 at 05:09

With the help of set we can easily implement it.

char[] ch = {'k', 'a', 'm', 'o', 'k', 'm', 'y', 'm', 'k', 'k', 'x', 'm', 'm', 'o'};
System.out.print("The original array is : ");
System.out.println(ch);

// Moving in to LinkedHashSet
Set<Character> charSet = new LinkedHashSet<Character>();
for(char c : ch) 
   charSet.add(c);

System.out.println("Number of deleted characters :"+(ch.length-charSet.size()));

// Move Back to newArray
char[] newch = new char[charSet.size()];
int i = 0;
for(char c : charSet)
   newch[i++] = c;

System.out.print("The new array is :");
System.out.println(newch);

Output:

The original array is : kamokmymkkxmmo
Number of deleted characters :8
The new array is :kamoyx

Java array and for loop causing wrong output

4 Answers4