Array Rotation in Go

This program demonstrates how to rotate an array by k positions using the Go programming language.

Explanation

Array rotation involves moving the elements of the array to the right by k positions. For example, if the array is [1, 2, 3, 4, 5] and k is 2, the rotated array will be [4, 5, 1, 2, 3].

The approach used in this program includes the following steps:

1. Reverse the entire array.
2. Reverse the first k elements.
3. Reverse the remaining elements.

This method ensures that the array is rotated in-place with a time complexity of O(n) and a space complexity of O(1).

Go Program

// Go program to rotate an array by k positions

package main

import (
    "fmt"
)

// Function to reverse a portion of the array
func reverse(arr []int, start int, end int) {
    for start < end {
        arr[start], arr[end] = arr[end], arr[start]
        start++
        end--
    }
}

// Function to rotate the array by k positions
func rotateArray(arr []int, k int) {
    n := len(arr)
    k = k % n // Handle cases where k is larger than n
    reverse(arr, 0, n-1)
    reverse(arr, 0, k-1)
    reverse(arr, k, n-1)
}

func main() {
    arr := []int{1, 2, 3, 4, 5}
    k := 2
    
    fmt.Println("Original array:", arr)
    rotateArray(arr, k)
    fmt.Println("Rotated array:", arr)
}

Output

The output of the above program will be:

Original array: [1 2 3 4 5]
Rotated array: [4 5 1 2 3]

Explanation of the Code

The program includes three main functions:

• reverse(arr []int, start int, end int): This function reverses the elements in the array from the index start to end.
• rotateArray(arr []int, k int): This function rotates the array by k positions. It first calculates the effective rotation using k = k % n to handle cases where k is larger than the array size. Then, it reverses the entire array, the first k elements, and the remaining elements.
• main(): This is the main function where the array and rotation value are defined. It prints the original array, calls the rotateArray function, and prints the rotated array.

This program demonstrates an efficient way to rotate an array by using in-place reversal. This method is both time and space efficient, making it suitable for large arrays.