Problem:
Given an array containing negative/zero/positive elements.
Now list all the start and end positions of the sub arrays, whose sum is equal to zero.
For eg:
{2, -1, 0, 1, 1, -1, -2}
Output:
start=2, end=2
start=1, end=3
start=1, end=5
start=4, end=5
start=0, end=6
Algorithm:
maintain HashMap with key as current sum and value as a list of index positions
3 cases possible for every element:
1. current element is zero: output is: start=currentPosition, end=currentPosition
2. current sum is zero: output is: start=0, end=currentPosition
3. current sum is already present in the hashMap, which means that the sub array formed by positions "hashMap.get(currentSum)+1" and "currentPosition" sum is zero. so print all such possibilities with hashMap values
If the sum is not present in the hashMap, then insert (sum, {currentPosition})
if the sum is already present, then insert (sum, {previously inserted positions, currentPosition})
Program:
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
class PrintPositions {
static public void printPos(int[] in) {
Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
int sum = 0;
for(int i=0; i<in.length; i++) {
sum = sum + in[i];
if(in[i] == 0)
System.out.println("start=" + i + ", end=" + i);
else if(sum == 0)
System.out.println("start=0, end=" + i);
else {
if(map.containsKey(sum)) {
List<Integer> positions = map.get(sum);
for(int pos : positions)
System.out.println("start=" + (pos+1) + ", end=" + i);
}
}
if(map.get(sum) == null) {
List<Integer> list = new ArrayList<Integer>();
list.add(i);
map.put(sum, list);
} else {
List<Integer> list = map.get(sum);
list.add(i);
}
}
}
static public void main(String[] args) {
PrintPositions pp = new PrintPositions();
pp.printPos(new int[]{2, -1, 0, 1, 1, -1, -2});
}
}
output:
start=2, end=2
start=1, end=3
start=1, end=5
start=4, end=5
start=0, end=6
start=1, end=7
start=4, end=7
start=6, end=7
Given an array containing negative/zero/positive elements.
Now list all the start and end positions of the sub arrays, whose sum is equal to zero.
For eg:
{2, -1, 0, 1, 1, -1, -2}
Output:
start=2, end=2
start=1, end=3
start=1, end=5
start=4, end=5
start=0, end=6
Algorithm:
maintain HashMap with key as current sum and value as a list of index positions
3 cases possible for every element:
1. current element is zero: output is: start=currentPosition, end=currentPosition
2. current sum is zero: output is: start=0, end=currentPosition
3. current sum is already present in the hashMap, which means that the sub array formed by positions "hashMap.get(currentSum)+1" and "currentPosition" sum is zero. so print all such possibilities with hashMap values
If the sum is not present in the hashMap, then insert (sum, {currentPosition})
if the sum is already present, then insert (sum, {previously inserted positions, currentPosition})
Program:
import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
class PrintPositions {
static public void printPos(int[] in) {
Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
int sum = 0;
for(int i=0; i<in.length; i++) {
sum = sum + in[i];
if(in[i] == 0)
System.out.println("start=" + i + ", end=" + i);
else if(sum == 0)
System.out.println("start=0, end=" + i);
else {
if(map.containsKey(sum)) {
List<Integer> positions = map.get(sum);
for(int pos : positions)
System.out.println("start=" + (pos+1) + ", end=" + i);
}
}
if(map.get(sum) == null) {
List<Integer> list = new ArrayList<Integer>();
list.add(i);
map.put(sum, list);
} else {
List<Integer> list = map.get(sum);
list.add(i);
}
}
}
static public void main(String[] args) {
PrintPositions pp = new PrintPositions();
pp.printPos(new int[]{2, -1, 0, 1, 1, -1, -2});
}
}
output:
start=2, end=2
start=1, end=3
start=1, end=5
start=4, end=5
start=0, end=6
start=1, end=7
start=4, end=7
start=6, end=7
No comments:
Post a Comment