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.