Recaman Sequence: n-th Term
Problem
The Recaman sequence starts with a(0) = 0. For n >= 1: look at a(n-1) - n. If it is positive and was not used before in the sequence, then a(n) = a(n-1) - n. Otherwise a(n) = a(n-1) + n. Print a(n). The sequence begins 0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, ...
Constraints
- 0 <= n <= 10^5
Examples
Input
4
Output
2
Input
10
Output
11
Solutions
The rule needs to ask: was this number used before? A set answers that in O(1), so the whole sequence is built in O(n) steps.
/*
* Problem : Find a(n).
* Input : n.
* Output : a(n).
* Approach: Set lookup
* Time : O(n)
* Space : O(n)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
// This method solves the task. It receives the input and returns the answer.
static long solve(long n) {
// Step 1: A set remembers every value that is already in the sequence.
java.util.Set<Long> seen = new java.util.HashSet<Long>();
long value = 0;
seen.add(0L);
for (long i = 1; i <= n; i++) {
// Step 2: Go down by i if the result is positive and new. Otherwise go up by i.
long down = value - i;
value = (down > 0 && !seen.contains(down)) ? down : value + i;
seen.add(value);
}
return value;
}
public static void main(String[] args) {
long n = new Scanner(System.in).nextLong();
System.out.println(solve(n));
}
}
Hints (1)
- What data structure answers 'seen before?' fast?