Arrays: Print in a Circular Array

Problem Statement:

You are given an array, and a name, you need to print all the people in the array staring from the given name.

We consider an array is circular, if we consider the first element as the next of the last element.

Example:

Input: arr = {a, b, c, d, e, f} name = "d"
Output: d, e, f, a, b, c

Here when the name is given as ‘d’, the people sitting in a circular manner, starting from d are d, e, f, a, b, c

Solution 1: Brute force method

You need to create an array of size 2*n and store in the array.

Example:

a b c e d f a b c d e f

Then for any given index, print the n elements starting from it.

In our example, it is ‘d’, hence we print all the elements starting from ‘d’.

a b c e d f a b c d e f
         _ _ _ _ _     

Time Complexity: O(n)

Space Complexity: O(n)

Solution 2: Efficient Approach

Instead of taking a new array, we can use the same array.

We can observe that, after nth index, the next index starts form 0 for a circular array.

So using the mod operator, we can access the elements of the circular list.

Time Complexity: O(n)

Space Complexity: O(1)

Code Solution

#include <iostream>

using namespace std; 
void solution_1(char a[], int n, int ind) 
{ 
    //create temp array
    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] << " "; 
        
    cout<<"\n";
} 

void solution_2(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]); 
    solution_1(a, n, 3); 
    solution_2(a, n, 3); 
    
    return 0; 
} 

Output

D E F A B C 
D E F A B C