Count of Range Sum Problem in Java
In this article, we will discuss the basic approach or native approach used to count range sum problem in java.
To solve this problem, we will check for numbers if they lie in between or the range lies in between I and R then we have to increase the count.
The procedure or algorithm is as follows:
- Set the variables count and temp to zero.
- iterate I from 0 to the array's size minus 1. This would determine where our subarrays would begin.
- Update temp=0, each time the loop runs.
- Repeat steps j from i until array-1's size. This would determine where our subarrays will terminate.
- The temporary variable as temp+=Nums[j];
- Increase count by 1 if temp>=L or temp=R.
- Return rate.
Example code:
import java.util.*;
import java.io.*;
public class TestRangeSum
{
public int countrange(int arr[], int n, int l, int r)
{
long temp = 0;
int count = 0;
for (int j = 0; j < n; j++)
{
temp = 0;
for (int i = j; i < n; i++)
{
//The ith index varies with each iteration, which causes the size of the sub-array to vary as well. As a result, the total also changes with each iteration, and these changes are reflected or stored in the temp variable.
temp = temp + arr[i];
// Increase the count by one if the amount is inside the range.
if(temp >= l && temp <= r)
{
count = count + 1;
}
}
}
return count;
}
public static void main(String args[])
{
TestRangeSum obj = new TestRangeSum();
int arr[] = {11, 12, 13, 14, 15, 16, 17};
int n = arr.length;
int l = 12;
int r = 17;
int answer = obj.countrange(arr, n, l, r);
System.out.println("the initial array: ");
for(int i = 0; i < n; i++)
{
System.out.print(arr[i] + " ");
}
System.out.println();
if(answer != 0)
{
System.out.print("The sum lies in range between "+ l + " & " + r + " is " + answer + ".");
}
else
{
System.out.print("There is no range whose sum lies between "+ l + " & " + r + ".");
}
System.out.println("\n");
int arr1[] = {111, 112, 113, 114, 115, 116, 117};
// the size
n = arr1.length;
l = 19;
r = 110;
answer = obj.countrange(arr1, n, l, r);
System.out.println("For initial array: ");
for(int i = 0; i < n; i++)
{
System.out.print(arr1[i] + " ");
}
System.out.println();
if(answer != 0)
{
System.out.print("The range in between between "+ l + " & " + r + " is " + answer + ".");
}
else
{
System.out.print("There is no range whose sum lies between "+ l + " & " + r + ".");
}
}
}
Output:
the initial array:
11 12 13 14 15 16 17
The sum lies in range between 12 & 17 is 6.
For initial array:
111 112 113 114 115 116 117
There is no range whose sum lies between 19 & 110.
To calculate the solution, we used nested for-loops. As a result, the program's time complexity is O(n2), where n is the total number of elements in the array. Additionally, we didn't employ a data structure to store the findings. As a result, the program's space complexity, which is O, is constant (1).
Another approach:
With this strategy, we'll strive to make the program's time complexity go from O (n2). In this approach, we merge the answers while counting the answers using merge sort. The left half [start, mid] and right half [mid, end] have previously been sorted at the merge stage. Then, using index I we iterate through the left half. It is necessary to calculate the two indices m and n in the right half for each I, where n is the first index that satisfies the condition sumArr[n] - sumArr[i] = right and k is the first index that satisfies the condition sumArr[m] - sumArr[i] left. So, n - m is the total number of sums in [left, right].
Process:
In this merge-sort approach, we count the response as we combine. The left half [start, mid] and right half [mid, end] have previously been sorted at the merge stage.
Then, using index I we iterate through the left half. To discover two indices k and j that satisfy sums[j] - sums[i] > R and k that satisfy sums[k] - sums[i] >= L for each I we must search the right half.
There is then j - k sums in [L, R].
Algorithm:
Step 1: A function for merging subarray counts; int mcount (int [] sum, int L, int R, int start, int end)
Step 2: First, handle the extreme situations; if end-start > 0, then return 0.
Step 3: Initialize the variable mid with the formula: mid = (start + end)/2, m = n, and mid.
Step 4: Create a variable called count, and then update it as follows: count=mcout(sum,L,R,start,mid) + mcount (sum,L,R,mid,end)
Step 5: Repeat step 1 from 0 to mid.
- As long as (m<end and sum[m]-sum[i]L) m++
- as long as (n<end and sum[n]-sum[i]=R) n++
- as count+=n-m, update the count.
Step 6: Return the count.
Step 7: CountRangeSum is a function that counts the number of sum ranges (int [] nums, int L, int R).
- Create an array of long ints with a length equal to nums+1 in order to prevent int overflows.
- Update sum as sum[i+1]=sum[i]+nums[i] as you iterate I from 0 to n.
- The value acquired by the previous function mcount(sum,L,R,0,n+1) is then returned.
// important import packages
import java.util.*;
import java.io.*;
import java.util.Arrays;
public class RangeSum
{
static int mergeSum(int arr[], int l, int r, int start, int end)
{
// base conditions
if (end - start <= 1)
{
return 0;
}
int mid = (start + end) / 2;
int a = mid;
int b = mid;
int count = mergeSum(arr, l, r, start, mid) + mergeSum(arr, l, r, mid, end);
// counting valid ranges
for (int j = start; j < mid; j++)
{
while (a < end && arr[a] - arr[j] < l)
{
a = a + 1;
}
while (b < end && arr[b] - arr[j] <= r)
{
b = b + 1;
}
count = count + b - a;
}
//combining the two sorted sections, then copying the sorted outcome back to the array arr[]
Arrays.sort(arr, start, end);
return count;
}
public static int findRangeSum(int narr[], int n, int l, int r)
{
int arr[] = new int[n + 1];
// initializing of the elements in the arr[] to 0
for (int i = 0; i < n + 1; i++)
{
arr[i] = 0;
}
// a computational loop the initial sum
//It is done so that we can rapidly calculate the range sum.
for (int j = 0; j < n; j++)
{
arr[j + 1] = arr[j] + narr[j];
}
return mergeSum(arr, l, r, 0, n + 1);
}
// main method
public static void main(String argvs[])
{
// creating an object of the class RangeSum
RangeSum obj = new RangeSum();
// input array
int narr[] = {10, 20, 30, 40, 50, 60, 70};
// size declaration
int n = narr.length;
// defining the boundaries i.e, the l and the r ranges
int l = 20;
int r = 70;
int ans = obj.findRangeSum(narr, n, l, r);
System.out.println("For the input array: ");
for(int i = 0; i < n; i++)
{
System.out.print(narr[i] + " ");
}
System.out.println();
if(ans != 0)
{
System.out.print("The number of ranges whose sum lies between "+ l + " & " + r + " is " + ans + ".");
}
else
{
System.out.print("There is no range whose sum lies between "+ l+ " & " + r + ".");
}
System.out.println("\n");
// input array
int narr1[] = {11, 12, 13, 14, 15, 16, 17};
// computing its size
n = narr1.length;
// defining the ranges, i.e, the left and the right boundary
l = 9;
r = 10;
// invoking the method findCountRangeSum() and storing the answer
ans = obj.findRangeSum(narr1, n, l, r);
System.out.println("input array: ");
for(int i = 0; i < n; i++)
{
System.out.print(narr1[i] + " ");
}
System.out.println();
if(ans != 0)
{
System.out.print("The range in between the sum lies is "+ l + " & " + r + " is " + ans + ".");
}
else
{
System.out.print("The range in between the sum does not lies is "+ l + " & " + r+ ".");
}
}
}
Output:
For the input array: 10 20 30 40 50 60 70
The number of ranges whose sum lies between 20 & 70 is 10.
input array:
11 12 13 14 15 16 17
The range in between the sum does not lies is 9 & 10.