Question: An array is said to be hollow if it contains 3 or more zeros in the middle that are preceded and followed by the same number of non-zero elements. Furthermore, all the zeroes in the array must be in the middle of the array. Write a function named isHollow that accepts an integer array and returns 1 if it is a hollow array, otherwise it returns 0.
If you are programming in Java or C#, the function signature is int isHollow(int[ ] a)
If you are programming in C or C++, the function signature is int isHollow(int a[ ], int len) where len is the number of elements in the array
Examples:
if the input array is | is hollow? | reason |
{1,2,0,0,0,3,4} | yes | 2 non-zeros precede and follow 3 zeros in the middle |
{1,1,1,1,0,0,0,0,0,2,1,2,18} | yes | 4 non-zeros precede and follow the 5 zeros in the middle |
{1, 2, 0, 0, 3, 4} | no | There are only 2 zeroes in the middle; at least 3 are required |
{1,2,0,0,0,3,4,5} | no | The number of preceding non-zeros(2) is not equal to the number of following non-zeros(3) |
{3,8,3,0,0,0,3,3} | no | The number of preceding non-zeros(3) is not equal to the number of following non-zeros(2) |
{1,2,0,0,0,3,4,0} | no | Not all zeros are in the middle |
{0,1,2,0,0,0,3,4} | no | Not all zeros are in the middle |
{0,0,0} | yes | The number of preceding non-zeros is 0 which equals the number of following non-zeros. And there are three zeros "in the middle". |
Hint: Write three loops. The first counts the number of preceding non-zeros. The second counts the number of zeros in the middle. The third counts the number of following non-zeros. Then analyze the results.
Answer & Solution:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | public class First { public static void main(String[] args) { System.out.println(isHollow(new int[] {1,2,0,0,0,3,4})); System.out.println(isHollow(new int[] {1,1,1,1,0,0,0,0,0,2,1,2,18})); System.out.println(isHollow(new int[] {1, 2, 0, 0, 3, 4})); System.out.println(isHollow(new int[] {1,2,0,0,0,3,4,5})); System.out.println(isHollow(new int[] {3,8,3,0,0,0,3,3})); System.out.println(isHollow(new int[] {1,2,0,0,0,3,4,0})); System.out.println(isHollow(new int[] {0,1,2,0,0,0,3,4})); System.out.println(isHollow(new int[] {0,0,0})); } static int isHollow(int[] a) { int count=a.length; int zerocount=0; int i; int j; int istart; int jstart; if(count%2==0){ istart=(count/2)-1; jstart=count/2; }else{ istart=count/2; jstart=count/2; } for(i=istart, j=jstart; i>=0; i--, j++){ if(a[i]==0 && a[j]==0) zerocount++; else if(a[i]!=0 && a[j]!=0){ break; }else{ zerocount=0; break; } } if(zerocount>1) return 1; else return 0; } } |
No comments:
Post a Comment