Queries on the Left and Right Circular Shift on Array in C++

This article discusses the method to perform left and right-shift on C++ arrays. Thereby, answer queries on the left and right circular shift on array in C++. The motive of the problem is to perform Queries on shifted-arrays after it is rotated by a constant number, say ‘k’ times in either left or the right direction. The queries may include normal shifting by ‘k’ elements, finding the sum of a sub-array.

Before moving into the solution, here are the names we will be using for the variables to explain the idea. ‘k’ is the number of elements by which the array is rotated. Let, ‘n’ be the size of the array considered. The trivial approach to solve the problem would be to use the brute force approach, wherein we rotate the array element-by-element for ‘k’ times. However, this approach is quite costly in terms of time complexity.

Hence, we are to come up with a better solution that can cut down unnecessary rotations whenever possible, and if possible make a net rotation instead. And yes, this is indeed a possibility.

 

Approach

What we have to do immediately is to cut down unnecessary rotations. This can be done quite easily by taking the mod of the size of the arrays, in the case take the input as mod n ( input % n). For example, say the size of the array is n = 10, and the value of k, which is the number of elements by which the array has to be rotated is k  = 12, according to the brute force solution, we have to make 12 rotations. However, if we check, on taking the mod, we get the value ‘2’ ( 12 % 10 ), which is indeed what we require. Since the shifting is circular, the first 10 rotations are needless in this case. So, our approach is immediately showing some promise.

 

1  2  3  4  5  6  7  8  9  0 

9  0  1  2  3  4  5  6  7  8 

 

Next, we try to avoid individual rotations. This can be done. We can do a net rotation instead of an element-wise shift. We have to keep a note of the indices of the elements and finally transfer the elements from the array to another based on the value of ‘k’. In the case of the sum of the sub-array, the only thing we have to keep a note of is to reset the index, once the index reaches the end.

Now, have a look at the code.

 

C++ Code for Queries on the left and right circular shift on array

The following is the code for various queries on Left and Right Circular Shift on Array in C++.

  1. Right-Shift 
    #include<iostream>
    using namespace std;
    
    int main()
    {
        int sizeArr;
    
        cout<<"ENTER NUMBER OF ELEMENTS : ";
        cin>>sizeArr;
    
        int k, a[sizeArr], sink[sizeArr];
    
        cout<<"ENTER THE ELEMENTS : ";
    
        for(int i=0;i<sizeArr;i++)
        {
            cin>>a[i];
        }
    
        cout<<"ENTER 'k' : ";
        cin>>k;
        k = k%sizeArr;
        cout<<"\n\n'k' : "<<k<<endl;
    
        int i = 0, j = 0;
    
        while(i<k)
        {
            sink[i] = a[sizeArr - k + i];
            i++;
        }
    
        while(j<sizeArr - k)
        {
            sink[i++] = a[j++];
        }
    
        for(int i=0;i<sizeArr;i++)
        {
            cout<<sink[i]<<" ";
        }
    
    
        return 0;
    }
    

    Below is the output result:

    ENTER NUMBER OF ELEMENTS : 5
    ENTER THE ELEMENTS : 1 3 5 4 7
    ENTER 'k' : 2
    
    
    'k' : 2
    4 7 1 3 5
  2. Left-Shift
    #include<iostream>
    using namespace std;
    
    int main()
    {
        int sizeArr;
    
        cout<<"ENTER NUMBER OF ELEMENTS : ";
        cin>>sizeArr;
    
        int k, a[sizeArr], sink[sizeArr];
    
        cout<<"ENTER THE ELEMENTS : ";
    
        for(int i=0;i<sizeArr;i++)
        {
            cin>>a[i];
        }
    
        cout<<"ENTER 'k' : ";
        cin>>k;
        k = k%sizeArr;
        cout<<"\n\n'k' : "<<k<<endl;
    
        int i = k, j = 0;
    
        while(i<sizeArr)
        {
            sink[j++] = a[i++];
        }
    
        i=0;
    
        while(i<k)
        {
            sink[j++] = a[i++];
        }
    
        for(int i=0;i<sizeArr;i++)
        {
            cout<<sink[i]<<" ";
        }
    
    
        return 0;
    }
    

    Below is what we can see after running the above code:

    ENTER NUMBER OF ELEMENTS : 5
    ENTER THE ELEMENTS : 1 3 5 4 7
    ENTER 'k' : 2
    
    
    'k' : 2
    5 4 7 1 3
  3. Sum of Sub-Array
    #include<iostream> 
    using namespace std; 
    
    int main() 
    { 
        int sizeArr; 
        int i; 
        int j; 
        int sum = 0; 
        int index = 0; 
        int counter = 0; 
        
        cout<<"ENTER THE SIZE OF THE ARRAY : "; 
        
        cin>>sizeArr; 
        int a[sizeArr]; 
    
        cout<<"ENTER THE ELEMENTS : "<<endl;
        
        for(int i=0;i<sizeArr;i++) 
        { 
            cin>>a[i]; 
        } 
        
        cout<<"ENTER THE BOUNDING INDICES : "; 
        cin>>i>>j; 
        index = i-1; 
        
        cout<<"SUBARRAY UNDER CONSIDERATION : { ";
        while(counter<abs(j-i)+ 1) 
        { 
            if(index == sizeArr) 
            { 
                index = 0; 
                
            } 
        cout<<a[index]<<" "; 
        
        sum += a[index]; 
        counter++; 
        index++; 
            
        } 
    cout<<"}"<<endl<<"SUM : "<<sum; 
    return 0; 
        
    }

    And the output is given below:

    ENTER THE SIZE OF THE ARRAY : 5
    
    ENTER THE ELEMENTS :
    
    1 3 5 4 7
    
    ENTER THE BOUNDING INDICES : 2 4
    
    SUBARRAY UNDER CONSIDERATION : { 3 5 4 }
    
    SUM : 12
    
    

Feel free to read the following articles:

 

Leave a Reply

Your email address will not be published. Required fields are marked *