Array Rotation and Sum
December 15, 2023
Problem #
Sure, here’s a mediumlevel algorithm interview question that I’ve created:
Problem: “Array Rotation and Sum”
You are given an array of n integers and a number, k. Your task is to write a function that rotates the array to the right by k steps, and then finds the sum of a specific subarray.
Specifically, your function should implement the following steps:
 Rotate the array to the right by k steps. For example, with the array
[1, 2, 3, 4, 5]
andk = 2
, the array after rotation would be[4, 5, 1, 2, 3]
.  After the rotation, find the sum of the elements between indices i and j (inclusive), where i and j are parameters to your function.
Your function should have the signature:
def rotate_and_sum(arr, k, i, j):
# Your code here
Where:
arr
is the list of integers.k
is the number of steps for the rotation.i
andj
are the indices for the subarray whose sum is to be found.
For example, given arr = [1, 2, 3, 4, 5]
, k = 2
, i = 1
, and j = 3
, your function should return the sum of the elements from index 1 to 3 in the rotated array [4, 5, 1, 2, 3]
, which is 5 + 1 + 2 = 8
.
Note: You need to consider the edge cases, such as when k
is larger than the array size, or i
and j
are out of bounds. The solution should be efficient in terms of time and space complexity.
Solution #
def rotate_and_sum(arr, k, i, j):
# Handle the case where k is greater than the length of the array
n = len(arr)
k = k % n
# Rotate the array
rotated_arr = arr[k:] + arr[:k]
# Validate the indices
if i < 0 or j >= n or i > j:
raise ValueError("Invalid indices i and j")
# Calculate the sum of the subarray
return sum(rotated_arr[i:j+1])
# Example usage
arr = [1, 2, 3, 4, 5]
k = 2
i = 1
j = 3
result = rotate_and_sum(arr, k, i, j)
print(f"Sum of the subarray from index {i} to {j} in the rotated array: {result}")
This function first handles the scenario where k
is larger than the array size by taking the modulus of k
with the array length. It then rotates the array to the right by k
steps and calculates the sum of the specified subarray. Note that the function also includes a check for valid index values i
and j
. If i
or j
are out of the array bounds, or if i
is greater than j
, it raises a ValueError
.
Solution Analysis: Step by Step #

Handle Large
k
Values: First, we consider the case where
k
(the number of steps to rotate the array) is larger than the length of the array. Ifk
is larger, rotating the arrayk
times would bring it back to its original position after everyn
rotations, wheren
is the length of the array. To handle this, we take the modulus ofk
withn
(k = k % n
). This step ensures that we only rotate the array the minimum required number of times.
 First, we consider the case where

Rotate the Array:
 The array is rotated by slicing it into two parts and then concatenating these parts in reversed order. If we split the array at the
n  k
th position (arr[k:]
andarr[:k]
), we get the lastk
elements and the firstnk
elements, respectively. By concatenating the lastk
elements in front of the firstnk
elements (rotated_arr = arr[k:] + arr[:k]
), we achieve the right rotation effect.
 The array is rotated by slicing it into two parts and then concatenating these parts in reversed order. If we split the array at the

Validate Indices
i
andj
: Before summing the elements, we check if the indices
i
andj
are valid. They must be within the array bounds (0 ton1
), andi
should not be greater thanj
. If these conditions are not met, aValueError
is raised. This is important to prevent accessing elements outside the array bounds and to ensure logical correctness (the start index should not be after the end index).
 Before summing the elements, we check if the indices

Calculate the Sum of the Subarray:
 Finally, the function calculates the sum of elements from index
i
toj
(inclusive) in the rotated array usingsum(rotated_arr[i:j+1])
. Thej+1
is used because in Python slicing, the end index is exclusive, so we need to go one index further to include the element at indexj
.
 Finally, the function calculates the sum of elements from index
The function then returns this sum, which represents the sum of the specified subarray in the rotated array.
Here’s an example to illustrate how it works:
 Given
arr = [1, 2, 3, 4, 5]
,k = 2
,i = 1
, andj = 3
.  After handling
k
,k
remains2
since2
is less than the length ofarr
(5
).  The array is rotated to
[4, 5, 1, 2, 3]
.  The sum of elements from index
1
to3
in this rotated array is5 + 1 + 2 = 8
.