Can I Create a Continuous Array

Circular array

View Discussion

Improve Article

Save Article

Like Article

Read

Discuss

View Discussion

Improve Article

Save Article

Like Article

An array is called circular if we consider the first element as next of the last element. Circular arrays are used to implement queue (Refer to this and this).
An example problem :
Suppose n people are sitting at a circular table with names A, B, C, D, … Given a name, we need to print all n people (in order) starting from the given name.

 For example, consider 6 people A B C D E F and given name as 'D'. People sitting in a circular manner starting from D are D E F A B C.
A simple solution is to create an auxiliary array of size 2*n and store it in another array. For example for 6 people, we create below the auxiliary array.
A B C D E F A B C D E F
Now for any given index, we simply print n elements starting from it. For example, we print the following 6.
A B C D E F A B C D E F

Below is the implementation of the above approach.

C++

#include <bits/stdc++.h>

using namespace std;

void print( char a[], int n, int ind)

{

char b[(2 * n)];

for ( int i = 0; i < n; i++)

b[i] = b[n + i] = a[i];

for ( int i = ind; i < n + ind; i++)

cout << b[i] << " " ;

}

int main()

{

char a[] = { 'A' , 'B' , 'C' , 'D' , 'E' , 'F' };

int n = sizeof (a) / sizeof (a[0]);

print(a, n, 3);

return 0;

}

Java

import java.util.*;

import java.lang.*;

public class GfG{

public static void print( char a[], int n,

int ind){

char [] b = new char [( 2 * n)];

for ( int i = 0 ; i < n; i++)

b[i] = b[n + i] = a[i];

for ( int i = ind; i < n + ind; i++)

System.out.print(b[i]+ " " );

}

public static void main(String argc[]){

char [] a = new char []{ 'A' , 'B' , 'C' ,

'D' , 'E' , 'F' };

int n = 6 ;

print(a, n, 3 );

}

}

Python3

def prints(a, n, ind):

b = [ None ] * 2 * n

i = 0

while i < n:

b[i] = b[n + i] = a[i]

i = i + 1

i = ind

while i < n + ind :

print (b[i], end = " " );

i = i + 1

a = [ 'A' , 'B' , 'C' , 'D' , 'E' , 'F' ]

n = len (a);

prints(a, n, 3 );

C#

using System;

public class GfG {

public static void print( char [] a, int n,

int ind)

{

char [] b = new char [(2 * n)];

for ( int i = 0; i < n; i++)

b[i] = b[n + i] = a[i];

for ( int i = ind; i < n + ind; i++)

Console.Write(b[i] + " " );

}

public static void Main()

{

char [] a = new char [] { 'A' , 'B' , 'C' ,

'D' , 'E' , 'F' };

int n = 6;

print(a, n, 3);

}

}

Javascript

<script>

function print( a , n , ind) {

var b = Array(2 * n);

for (i = 0; i < n; i++)

b[i] = b[n + i] = a[i];

for (i = ind; i < n + ind; i++)

document.write(b[i] + " " );

}

var a = [ 'A' , 'B' , 'C' , 'D' , 'E' , 'F' ];

var n = 6;

print(a, n, 3);

</script>

Output:

D E F A B C          

This approach takes of O(n) time but takes extra space of order O(n)

An efficient solution is to deal with circular arrays using the same array. If a careful observation is run through the array, then after n-th index, the next index always starts from 0 so using the mod operator, we can easily access the elements of the circular list, if we use (i)%n and run the loop from i-th index to n+i-th index. and apply mod we can do the traversal in a circular array within the given array without using any extra space.

C++

#include <bits/stdc++.h>

using namespace std;

void print( char a[], int n, int ind)

{

for ( int i = ind; i < n + ind; i++)

cout << a[(i % n)] << " " ;

}

int main()

{

char a[] = { 'A' , 'B' , 'C' , 'D' , 'E' , 'F' };

int n = sizeof (a) / sizeof (a[0]);

print(a, n, 3);

return 0;

}

Java

import java.util.*;

import java.lang.*;

public class GfG{

public static void print( char a[], int n,

int ind){

for ( int i = ind; i < n + ind; i++)

System.out.print(a[(i % n)] + " " );

}

public static void main(String argc[]){

char [] a = new char []{ 'A' , 'B' , 'C' ,

'D' , 'E' , 'F' };

int n = 6 ;

print(a, n, 3 );

}

}

Python3

def prints(a, n, ind):

i = ind

while i < n + ind :

print (a[(i % n)], end = " " )

i = i + 1

a = [ 'A' , 'B' , 'C' , 'D' , 'E' , 'F' ]

n = len (a);

prints(a, n, 3 );

C#

using System;

public class GfG {

public static void print( char [] a, int n,

int ind)

{

for ( int i = ind; i < n + ind; i++)

Console.Write(a[(i % n)] + " " );

}

public static void Main()

{

char [] a = new char [] { 'A' , 'B' , 'C' ,

'D' , 'E' , 'F' };

int n = 6;

print(a, n, 3);

}

}

PHP

<?php

function print ( $a , $n , $ind )

{

for ( $i = $ind ; $i < $n + $ind ; $i ++)

echo $a [( $i % $n )] . " " ;

}

$a = array ( 'A' , 'B' , 'C' ,

'D' , 'E' , 'F' );

$n = count ( $a );

print ( $a , $n , 3);

?>

Javascript

<script>

function print(a, n, ind)

{

for ( var i = ind; i < n + ind; i++)

document.write(a[parseInt(i % n)] + " " );

}

var a =[ 'A' , 'B' , 'C' , 'D' , 'E' , 'F' ];

var n = 6;

print(a, n, 3);

</script>

Output :

D E F A B C          

This approach takes O(n) time and O(1) extra space.
More problems based on circular array :

• Maximum circular subarray sum
• Maximize sum of consecutive differences in a circular array
• Implementation of Deque using circular array
• Circular Queue | Set 1 (Introduction and Array Implementation)
• Circular Queue | Set 2 (Circular Linked List Implementation)
• Find the Longest Increasing Subsequence in Circular manner
• Minimum absolute difference of adjacent elements in a circular array

Recent articles on circular array.

martingioncy.blogspot.com

Source: https://www.geeksforgeeks.org/circular-array/

Share this post