Traverse array in reverse, without minus sign

Question

Was asked this during a job interview today. I'm sure it's a pretty simple trick, but I couldn't think of it. How can I traverse a simple Java array from end to beginning (for example, in order to aggregate the sum of all values form right to left), without using the "minus" (-) sign (so no i-- in the loop, or something similar)?

Edit: I'm pretty sure it was supposed to be a trick that doesn't involve Java-specific structures (like Collections). Unfortunately I thought I'd think of it myself later, so I didn't ask what the answer was :/

If you are allowed to make use of `Collections`, you can convert the `array ` to `ArrayList`, reverse the list using Collection's `reverse` method and iterate it . — Jimmy, Sep 25 '17 at 15:26
Possible duplicate of [Iterating through a list in reverse order in java](https://stackoverflow.com/questions/2102499/iterating-through-a-list-in-reverse-order-in-java) — Silvio Mayolo, Sep 25 '17 at 15:27
Possible duplicate of [Can one do a for each loop in java in reverse order?](https://stackoverflow.com/questions/1098117/can-one-do-a-for-each-loop-in-java-in-reverse-order) — Procrastinator, Sep 25 '17 at 15:28
I'm guessing that if there was an answer without using Java-specific tools like `Collections` someone would have mentioned it. Should I accept the answer? — Cauthon, Sep 25 '17 at 15:32

score 9 · Accepted Answer · answered Sep 25 '17 at 15:36

Recursion is an option:

int[] numbers = {0,1,2,3,4,5,6,7,8,9,10};

public void traverseReversed(int[] a) {
    traverseReversed(a, 0);
}

private void traverseReversed(int[] a, int i) {
    if ( i + 1 < a.length ) {
        // Traverse the rest of the array first.
        traverseReversed(a, i+1);
    }
    System.out.println(a[i]);
}

public void test() throws Exception {
    System.out.println("Hello world!");
    traverseReversed(numbers);
}

Haven't thought of recursion :) – Cauthon Sep 25 '17 at 15:38 — Cauthon, Sep 25 '17 at 15:38

score 3 · Answer 2 · answered Sep 25 '17 at 15:28

3

If you are allowed to use Collections you can easily reverse it. Please see the below code -

Collections.reverse(Arrays.asList(array))

answered Sep 25 '17 at 15:28

Naseef Chowdhury

2,357
3
28
52

1

This reverses it in place, which not only destroys the original array's order, but also costs more than simply iterating it in reverse. – Makoto Sep 25 '17 at 15:45
Yes you are right. I am new in Java. I thought it is a possible answer, as there is no mention of keeping original order in the OP. – Naseef Chowdhury Sep 25 '17 at 15:53

Arnaud · Answer 3 · 2017-09-25T17:08:14.210

3

Don't know if the question in the interview is even a bit wise, but this answer will somehow.

Just use the ~ unary bitwise complement operator to obtain your custom -1 :

String[] array = {"aaa","bbb","ccc"};

int minusOne = ~0;// unary bitwise complement, yields -1


for(int i = array.length + minusOne; i >= 0; i = i + minusOne){

    System.out.println(array[i]);
}

edited Sep 25 '17 at 17:08

answered Sep 25 '17 at 16:06

Arnaud

17,229
3
31
44

score 2 · Answer 4 · answered Sep 25 '17 at 15:30

2

If you are allowed to use library like @Naseef mentioned, you can also use Common Lang and reverse array as:

ArrayUtils.reverse(int[] array)

answered Sep 25 '17 at 15:30

Yogen Rai

2,961
3
25
37

This reverses it in place, which not only destroys the original array's order, but also costs more than simply iterating it in reverse. – Makoto Sep 25 '17 at 15:45

tevemadar · Answer 5 · 2017-09-25T15:40:40.813

2

If you have enough stack space, you can always use recursion, and process the elements on your "way out"

void walkArray(int a[],int i){
  if(i+1<a.length)walkArray(a,i+1);
  System.out.println(a[i]);
}

EDIT, just to make sure: code would be launched as walkArray(a,0)

edited Sep 25 '17 at 15:40

answered Sep 25 '17 at 15:33

tevemadar

12,389
3
21
49

1

you missed the **reverse** part – Fureeish Sep 25 '17 at 15:34
1

@Fureeish I wonder how you define reverse if not the way that a 3-element array will be traversed as ```a[2], a[1], a[0]``` with this code – tevemadar Sep 25 '17 at 15:37
You are indeed correct. My apologies. For some reason I thought you are using *print* statement before the recursion – Fureeish Sep 25 '17 at 15:51

score 1 · Answer 6 · answered Sep 25 '17 at 16:51

You can use bitwise arithmetic if you don't want to use recursion. The trick lies in the bitwise not operator. Basically it negates the number and subtracts one from it. So ~(~i+1) is the same as -(-i-1+1)-1 which simplifies to i-1.

int i = array.length;
while(i > 0) {
  i = ~(~i + 1);
  System.out.println(array[i]);
}

Traverse array in reverse, without minus sign

6 Answers6