Given an integer n. Print first n elements of Recaman’s sequence.
Examples:
Input : n = 6
Output : 0, 1, 3, 6, 2, 7
Input : n = 17
Output : 0, 1, 3, 6, 2, 7, 13, 20, 12, 21,
11, 22, 10, 23, 9, 24, 8
It is basically a function with domain and co-domain as natural numbers and 0. It is recursively defined as below:
Specifically, let a(n) denote the (n+1)-th term. (0 is already there).
The rule says:
a(0) = 0,
if n > 0 and the number is not
already included in the sequence,
a(n) = a(n - 1) - n
else
a(n) = a(n-1) + n.
Below is a simple implementation where we store all n Recaman Sequence numbers in an array. We compute the next number using the recursive formula mentioned above.
C++
#include <bits/stdc++.h>
using namespace std;
int recaman(int n)
{
int arr[n];
arr[0] = 0;
printf("%d, ", arr[0]);
for (int i=1; i< n; i++)
{
int curr = arr[i-1] - i;
int j;
for (j = 0; j < i; j++)
{
if ((arr[j] == curr) || curr < 0)
{
curr = arr[i-1] + i;
break;
}
}
arr[i] = curr;
printf("%d, ", arr[i]);
}
}
int main()
{
int n = 17;
recaman(n);
return 0;
}
|
Java
import java.io.*;
class GFG {
static void recaman(int n)
{
int arr[] = new int[n];
arr[0] = 0;
System.out.print(arr[0]+" ,");
for (int i = 1; i < n; i++)
{
int curr = arr[i - 1] - i;
int j;
for (j = 0; j < i; j++)
{
if ((arr[j] == curr) || curr < 0)
{
curr = arr[i - 1] + i;
break;
}
}
arr[i] = curr;
System.out.print(arr[i]+", ");
}
}
public static void main (String[] args)
{
int n = 17;
recaman(n);
}
}
|
Python 3
def recaman(n):
arr = [0] * n
arr[0] = 0
print(arr[0], end=", ")
for i in range(1, n):
curr = arr[i-1] - i
for j in range(0, i):
if ((arr[j] == curr) or curr < 0):
curr = arr[i-1] + i
break
arr[i] = curr
print(arr[i], end=", ")
n = 17
recaman(n)
|
C#
using System;
class GFG {
static void recaman(int n)
{
int []arr = new int[n];
arr[0] = 0;
Console.Write(arr[0]+" ,");
for (int i = 1; i < n; i++)
{
int curr = arr[i - 1] - i;
int j;
for (j = 0; j < i; j++)
{
if ((arr[j] == curr) || curr < 0)
{
curr = arr[i - 1] + i;
break;
}
}
arr[i] = curr;
Console.Write(arr[i]+", ");
}
}
public static void Main ()
{
int n = 17;
recaman(n);
}
}
|
PHP
<?php
function recaman($n)
{
$arr[0] = 0;
echo $arr[0], ", ";
for ($i = 1; $i < $n; $i++)
{
$curr = $arr[$i - 1] - $i;
$j;
for ($j = 0; $j < $i; $j++)
{
if (($arr[$j] == $curr) || $curr < 0)
{
$curr = $arr[$i-1] + $i;
break;
}
}
$arr[$i] = $curr;
echo $arr[$i], ", ";
}
}
$n = 17;
recaman($n);
?>
|
Javascript
<script>
function recaman(n)
{
let arr = new Array(n);
arr[0] = 0;
document.write(arr[0]+" ,");
for (let i = 1; i < n; i++)
{
let curr = arr[i - 1] - i;
let j;
for (j = 0; j < i; j++)
{
if ((arr[j] == curr) || curr < 0)
{
curr = arr[i - 1] + i;
break;
}
}
arr[i] = curr;
document.write(arr[i]+", ");
}
}
let n = 17;
recaman(n);
</script>
|
Output:
0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24, 8,
Time Complexity : O(n2)
Auxiliary Space : O(n), since n extra space has been added
Optimizations :
We can use hashing to store previously computed values and can make this program work in O(n) time.
C++
#include <bits/stdc++.h>
using namespace std;
void recaman(int n)
{
if (n <= 0)
return;
printf("%d, ", 0);
unordered_set<int> s;
s.insert(0);
int prev = 0;
for (int i=1; i< n; i++)
{
int curr = prev - i;
if (curr < 0 || s.find(curr) != s.end())
curr = prev + i;
s.insert(curr);
printf("%d, ", curr);
prev = curr;
}
}
int main()
{
int n = 17;
recaman(n);
return 0;
}
|
Java
import java.util.*;
class GFG
{
static void recaman(int n)
{
if (n <= 0)
return;
System.out.printf("%d, ", 0);
HashSet<Integer> s = new HashSet<Integer>();
s.add(0);
int prev = 0;
for (int i = 1; i< n; i++)
{
int curr = prev - i;
if (curr < 0 || s.contains(curr))
curr = prev + i;
s.add(curr);
System.out.printf("%d, ", curr);
prev = curr;
}
}
public static void main(String[] args)
{
int n = 17;
recaman(n);
}
}
|
Python3
def recaman(n):
if(n <= 0):
return
print(0, ",", end='')
s = set([])
s.add(0)
prev = 0
for i in range(1, n):
curr = prev - i
if(curr < 0 or curr in s):
curr = prev + i
s.add(curr)
print(curr, ",", end='')
prev = curr
if __name__=='__main__':
n = 17
recaman(n)
|
C#
using System;
using System.Collections.Generic;
class GFG
{
static void recaman(int n)
{
if (n <= 0)
return;
Console.Write("{0}, ", 0);
HashSet<int> s = new HashSet<int>();
s.Add(0);
int prev = 0;
for (int i = 1; i < n; i++)
{
int curr = prev - i;
if (curr < 0 || s.Contains(curr))
curr = prev + i;
s.Add(curr);
Console.Write("{0}, ", curr);
prev = curr;
}
}
public static void Main(String[] args)
{
int n = 17;
recaman(n);
}
}
|
PHP
<?php
function recaman($n)
{
if($n <= 0)
return;
print("0, ");
$s = array();
array_push($s, 0);
$prev = 0;
for ($i = 1; $i < $n; $i++)
{
$curr = $prev - $i;
if($curr < 0 or in_array($curr, $s))
$curr = $prev + $i;
array_push($s, $curr);
print($curr.", ");
$prev = $curr;
}
}
$n = 17;
recaman($n);
?>
|
Javascript
<script>
function recaman(n)
{
if (n <= 0)
return;
document.write(0 + ", ");
let s = new Set();
s.add(0);
let prev = 0;
for (let i = 1; i< n; i++)
{
let curr = prev - i;
if (curr < 0 || s.has(curr))
curr = prev + i;
s.add(curr);
document.write(curr + ", ");
prev = curr;
}
}
let n = 17;
recaman(n);
</script>
|
Output:
0, 1, 3, 6, 2, 7, 13, 20, 12, 21, 11, 22, 10, 23, 9, 24, 8,
Time Complexity : O(n)
Auxiliary Space : O(n), since n extra space has been taken.