Custom Iterator: Stepped Range

Problem

Make a range that you can walk with a for loop. A range has a start, an end (not included) and a step (positive). Print all the values, in order. Input: start, end and step; the range always has at least one value.

Constraints

  • 0 <= start < end <= 10^6
  • 1 <= step <= 10^6

Examples

Input

0 5 1

Output

0 1 2 3 4

Solutions

Best approachTime O(n)Space O(n)

The loop does not know how the values are made. It asks the iterator: is there a next value, and what is it? The iterator class hides the position and the step.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Walk the range.
 * Input   : Start, end, step.
 * Output  : The values.
 * Approach: Iterator class
 * Time    : O(n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;
import java.util.Arrays;
import java.util.stream.Collectors;

public class Main {
        // Step 1: A class that implements Iterator can be used in a for-each loop (through Iterable).
        static class SteppedRange implements Iterable<Integer> {
            private final int start;
            private final int end;
            private final int step;

            SteppedRange(int start, int end, int step) {
                this.start = start;
                this.end = end;
                this.step = step;
            }

            @Override
            public java.util.Iterator<Integer> iterator() {
                // Step 2: The iterator keeps its own position, so every loop starts again from the beginning.
                return new java.util.Iterator<Integer>() {
                    private int next = start;

                    @Override
                    public boolean hasNext() {
                        return next < end;
                    }

                    @Override
                    public Integer next() {
                        int value = next;
                        next += step;
                        return value;
                    }
                };
            }
        }

    // This method solves the task. It receives the input and returns the answer.
    static int[] solve(long a, long b, long m) {
        // Step 3: The caller only writes a normal for-each loop.
        java.util.List<Integer> values = new java.util.ArrayList<Integer>();
        for (int value : new SteppedRange((int) a, (int) b, (int) m)) {
            values.add(value);
        }
        int[] out = new int[values.size()];
        for (int i = 0; i < out.length; i++) {
            out[i] = values.get(i);
        }
        return out;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long a = scanner.nextLong();
        long b = scanner.nextLong();
        long m = scanner.nextLong();
        System.out.println(Arrays.stream(solve(a, b, m)).mapToObj(String::valueOf).collect(Collectors.joining(" ")));
    }
}
Hints (2)
  1. Where is the current position kept?
  2. What stops the loop?