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++
// CPP program to demonstrate use of circular
// array using extra memory space
#include <bits/stdc++.h>
usingnamespacestd;
voidprint(chara[], intn, intind)
{
// Create an auxiliary array of twice size.
charb[(2 * n)];
// Copy a[] to b[] two times
for(inti = 0; i < n; i++)
b[i] = b[n + i] = a[i];
// print from ind-th index to (n+i)th index.
for(inti = ind; i < n + ind; i++)
cout << b[i] << " ";
}
// Driver code
intmain()
{
chara[] = { 'A', 'B', 'C', 'D', 'E', 'F'};
intn = sizeof(a) / sizeof(a[0]);
print(a, n, 3);
return0;
}
Java
// Java program to demonstrate use of circular
// array using extra memory space
importjava.util.*;
importjava.lang.*;
publicclassGfG{
publicstaticvoidprint(chara[], intn,
intind){
// Create an auxiliary array
// of twice size.
char[] b = newchar[(2* n)];
// Copy a[] to b[] two times
for(inti = 0; i < n; i++)
b[i] = b[n + i] = a[i];
// print from ind-th index to
// (n+i)th index.
for(inti = ind; i < n + ind; i++)
System.out.print(b[i]+" ");
}
// Driver code
publicstaticvoidmain(String argc[]){
char[] a = newchar[]{ 'A', 'B', 'C',
'D', 'E', 'F'};
intn = 6;
print(a, n, 3);
}
}
/* This code is contributed by Sagar Shukla */
Python3
# Python3 program to demonstrate use of
# circular array using extra memory space
defprints(a, n, ind):
# Create an auxiliary array of twice size.
b =[None]*2*n
i =0
# Copy a[] to b[] two times
whilei < n:
b[i] =b[n +i] =a[i]
i =i +1
i =ind
# print from ind-th index to (n+i)th index.
whilei < n +ind :
print(b[i], end =" ");
i =i +1
# Driver Code
a =['A', 'B', 'C', 'D', 'E', 'F']
n =len(a);
prints(a, n, 3);
#This code is contributed by rishabh_jain
C#
// C# program to demonstrate use of circular
// array using extra memory space
usingSystem;
publicclassGfG {
publicstaticvoidprint(char[] a, intn,
intind)
{
// Create an auxiliary array
// of twice size.
char[] b = newchar[(2 * n)];
// Copy a[] to b[] two times
for(inti = 0; i < n; i++)
b[i] = b[n + i] = a[i];
// print from ind-th index to
// (n+i)th index.
for(inti = ind; i < n + ind; i++)
Console.Write(b[i] + " ");
}
// Driver code
publicstaticvoidMain()
{
char[] a = newchar[] { 'A', 'B', 'C',
'D', 'E', 'F'};
intn = 6;
print(a, n, 3);
}
}
/* This code is contributed by vt_m*/
Javascript
// Function to print the circular rotation of array
functionprint(a, n, ind) {
// Create an auxiliary array of twice size.
let b = newArray(2 * n);
// Copy the input array 'a' to the auxiliary array 'b' twice
// so that we can rotate the array circularly
for(let i = 0; i < n; i++)
b[i] = b[n + i] = a[i];
// print from the `ind-th` index to the `(n+ind)th` index in the auxiliary array 'b'.
let output = '';
for(let i = ind; i < n + ind; i++)
output += b[i] + ' ';
console.log(output);
}
// Driver code
let a = ['A', 'B', 'C', 'D', 'E', 'F'];
let n = a.length;
// Call the function and pass the input array, its size, and the index to rotate.
print(a, n, 3);
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++
// CPP program to demonstrate the use of circular
// array without using extra memory space
#include <bits/stdc++.h>
usingnamespacestd;
// function to print circular list starting
// from given index ind.
voidprint(chara[], intn, intind)
{
// print from ind-th index to (n+i)th index.
for(inti = ind; i < n + ind; i++)
cout << a[(i % n)] << " ";
}
// Driver code
intmain()
{
chara[] = { 'A', 'B', 'C', 'D', 'E', 'F'};
intn = sizeof(a) / sizeof(a[0]);
print(a, n, 3);
return0;
}
Java
// Java program to demonstrate use of circular
// array using extra memory space
importjava.util.*;
importjava.lang.*;
publicclassGfG{
// function to print circular list
// starting from given index ind.
publicstaticvoidprint(chara[], intn,
intind){
// print from ind-th index to
// (n+i)th index.
for(inti = ind; i < n + ind; i++)
System.out.print(a[(i % n)] + " ");
}
// driver code
publicstaticvoidmain(String argc[]){
char[] a = newchar[]{ 'A', 'B', 'C',
'D', 'E', 'F'};
intn = 6;
print(a, n, 3);
}
}
/* This code is contributed by Sagar Shukla */
Python3
# Python3 program to demonstrate the use of
# circular array without using extra memory space
# function to print circular list starting
# from given index ind.
defprints(a, n, ind):
i =ind
# print from ind-th index to (n+i)th index.
whilei < n +ind :
print(a[(i %n)], end =" ")
i =i +1
# Driver Code
a =['A', 'B', 'C', 'D', 'E', 'F']
n =len(a);
prints(a, n, 3);
# This code is contributed by rishabh_jain
C#
// C# program to demonstrate use of circular
// array without using extra memory space
usingSystem;
publicclassGfG {
// function to print circular list
// starting from given index ind.
publicstaticvoidprint(char[] a, intn,
intind)
{
// print from ind-th index to
// (n+i)th index.
for(inti = ind; i < n + ind; i++)
Console.Write(a[(i % n)] + " ");
}
// driver code
publicstaticvoidMain()
{
char[] a = newchar[] { 'A', 'B', 'C',
'D', 'E', 'F'};
intn = 6;
print(a, n, 3);
}
}
/* This code is contributed by vt_m */
Javascript
// function to print circular list
// starting from given index ind.
functionprint(a, n, ind) {
// print from ind-th index to
// (n+i)th index.
for(vari = 0; i < n; i++) {
console.log(a[(ind + i) % n] + " ");
}
}
// Driver code
vara = ['A', 'B', 'C', 'D', 'E', 'F'];
varn = 6;
print(a, n, 3);
Output
D E F A B C
This approach takes O(n) time and O(1) extra space. More problems based on circular array :
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
