The problem “Print modified array after multiple array range increment operations” states that you are given an integer array and ‘q’ numbers of queries are given. One integer value “d” is also given. Each query contains two integers, starting value and an ending value. The problem statement asks to find out increase all the values in the array within the given range by the value “d”. Print the modified array.
Table of Contents
Example
arr[] = {2, 5, 1, 4, 7, 9}
Query: (1, 2), (3, 5), (4, 5), (2, 4), (1, 3)
d = 22 9 7 10 13 13
Explanation
After incrementing from index (1,2) arr will be {2, 7, 3, 4, 7, 9}
Now increment from index (3,5) arr will become {2, 7, 3, 6, 9, 11}
Again increase from index (4,5) arr will be {2, 7, 3, 6, 11, 13}
Now increment from index (2,4) arr will become {2, 7, 5, 8, 13, 13}
Again increase from index (1,3) arr will be {2, 9, 7, 10, 13, 13}
Algorithm for multiple array range increment operations
- Declare an array as the same size as the given array.
- Traverse the array from 0 to the total number of queries.
- Add the given value in the array we created to the given range. Check if the ending range of the given query is less than the length of the array. If true, decrease the value “d” from the array we created.
- Traverse the given array and update the output array with the addition of the current and the previous values and the given array.
- Print the updated array.
Explanation
Given an array of integer and some number of queries, each query contains the starting and ending range and a given value. We have to add up the given value to all of the numbers from the starting point to the ending point of the given range. We will be creating an array of queries. Two of the number will be associated with each of the query’s array. We will be creating an extra array of the same size as the length of the given array. We will perform the operations on this array and then update these operations on the given array.
Now we run a loop until the number of queries. We will update the output array with the addition of the given value d, at the starting index of the query. Check if the ending value of the query is less than the length of the array. If it is found to be true if true then decrease the d from the previously updated value in the output array. This is to make sure we will not go out of the range and the values.
Now, we are going to update the given array’s first position to the output array first position. Because we are going to traverse the sum (or output) array’s previous values and the current value. So we already updated the first value and now traverse from the first position of the output array until the end. We gonna add up the previous and current value and store it in the output array. Then copy that value to the given array’s respective positions while traversing. Print the modified array.
Code
C++ code to print modified array after multiple array range increment operations
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
struct query
{
int start, end;
};
void incrementByD(int arr[], struct query q_arr[],int n, int m, int d)
{
int sum[n];
memset(sum, 0, sizeof(sum));
for (int i = 0; i < m; i++)
{
sum[q_arr[i].start] += d;
if ((q_arr[i].end + 1) < n)
sum[q_arr[i].end + 1] -= d;
}
arr[0] += sum[0];
for (int i = 1; i < n; i++)
{
sum[i] += sum[i - 1];
arr[i] += sum[i];
}
}
void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
int main()
{
int arr[] = {2, 5, 1, 4, 7, 9};
struct query q_arr[] = { { 1, 2 }, { 3, 5 }, {4,5 },
{ 2, 4 }, { 1, 3 }
};
int n = sizeof(arr) / sizeof(arr[0]);
int m = sizeof(q_arr) / sizeof(q_arr[0]);
int d = 2;
cout << "Original Array:\n";
printArray(arr, n);
incrementByD(arr, q_arr, n, m, d);
cout << "\nModified Array:\n";
printArray(arr, n);
return 0;
}
Original Array: 2 5 1 4 7 9 Modified Array: 2 9 7 10 13 13
Java code to print modified array after multiple array range increment operations
class modifiedArray
{
static class query
{
int start, end;
query(int start, int end)
{
this.start = start;
this.end = end;
}
}
public static void incrementByD(int[] arr, query[] q_arr, int n, int m, int d)
{
int[] sum = new int[n];
for (int i = 0; i < m; i++)
{
sum[q_arr[i].start] += d;
if ((q_arr[i].end + 1) < n)
sum[q_arr[i].end + 1] -= d;
}
arr[0] += sum[0];
for (int i = 1; i < n; i++)
{
sum[i] += sum[i - 1];
arr[i] += sum[i];
}
}
public static void printArray(int[] arr, int n)
{
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
public static void main(String[] args)
{
int[] arr = { 2, 5, 1, 4, 7, 9};
query[] q_arr = {new query(1, 2),new query(3,5),new query(4, 5),
new query(2, 4),new query(1, 3)
};
int n = arr.length;
int m = q_arr.length;
int d = 2;
System.out.println("Original Array:");
printArray(arr, n);
incrementByD(arr, q_arr, n, m, d);
System.out.println("\nModified Array:");
printArray(arr, n);
}
}
Original Array: 2 5 1 4 7 9 Modified Array: 2 9 7 10 13 13
Complexity Analysis
Time Complexity
O(q+n) where “n” is the number of elements in the array and “q” is the number of queries. Since we have used an approach like a prefix sum, we have linear time complexity.
Space Complexity
O(n) where “n” is the number of elements in the array.