Given an array
$array = [ 0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0];
What is the quickest algorithm to group all the 0s and represent them as their starting and ending index?
(ie) Output of this should be (0,5),(10,17)...
Pseudo-code will be something like this -
for(int i = 0; i < array.length; i++) {
if(array[i] == 0) {
int left = i;
while(i + 1 < array.length && array[i + 1] == 0) {
i++;
}
// print range [left, i]
}
}
Time complexity is O(n) where n is array length. Space complexity is constant.
try this buddy...!! hope its fine :D
#include <stdio.h>
int main()
{
int a[12] = {0,0,0,0,1,1,1,1,0,0,0,0};
int i;
int t = 0;
for( i = 0; i < (int)( sizeof(a) / sizeof(a[0])); i++) {
if(a[i] == t) {
int k = i;
while(i + 1 < (int)( sizeof(a) / sizeof(a[0])) && a[i + 1] == 0) {
i++;
}
printf("range(%d,%d)\n",k,i);
}
}
}
Let me write multithreaded approach in pseudo-code form:
Function ZeroHunter()
Split the array into N segments (where N is multiple of number of threads available)
Create a Dictionary<SegmentNumber, Result>. Let's call it DicResults.
For i = 0 to Number of segments
Result = ProcessSegmentOnNewThread(S)
DicResults.Add(i, Result)
Next
Wait for all threads to complete
ConcatResults(DicResults)
End Function
Code for ProcessSegmentOnNewThread:
Function ProcessSegmentOnNewThread(Segment S)
Create a new thread
List<int, int> lst;
while i < S.Length
if S[i] == 0 Then
NewEntry = lst.Add(i, i)
while i < S.Length and S[i] == 0
NewEntry.End++;
i++
end while
end if
i++
end while
Return the results in the form of List<int, int>
End Function
Code for ConcatResults():
Function ConcatResults(DicResults)
Sort the input dictionary on segment number (the dictionary key that is)
For i = 0 to DicResults.Count - 1
If DicResult[i].End = DicResult[i+1].Start - 1
Set DicResult[i].End = DicResult[i+1].End
Remove DicResult[i+1] from the dictionary
End If
Next
Return DicResult
End Function
Thing to note is that while this algorithm will beat non-threaded algorithms for very large arrays, you should not use it for smaller arrays because the overhead of creating threads and joining the results will outweigh the potential benefit of threading.
