So i have an assignment, i need to turn all 1's in an array into the distance from the closest 0. And so when i run it, the last number in the output stays as 1, when it should have changed into a 2. can someone help me spot my mistake?
Basically what zeroDistance does, is pass the array once, changing all values, then runs from the back and changes them all again.
public static void zeroDistance (int [] a)
{
int counter = 0;
for (int i = 0; i < a.length; i++)
{
if (a[i] == 0)
counter = 0;
if (a[i] == 1)
{
counter++;
a[i] = counter;
}
}
counter = 0;
for (int i = a.length - 1; i >= 0; i--)
{
if (a[i] == 0)
counter = 0;
if (a[i] != 0)
{
counter++;
if (a[i] > counter)
a[i] = counter;
}
}
}
Input:
int[] a={0,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1};
Output:
zeroDistance method result :
0, 1, 2, 3, 3, 2, 1, 0, 1, 2, 3, 2, 1, 0, 1, 1
Should return :
0, 1, 2, 3, 3, 2, 1, 0, 1, 2, 3, 2, 1, 0, 1, 2
Your problem comes from the second loop. Since you start over from the end of the array, your second loop considers that you have encountered a 0 at the end of your array, which is obviously not the case here.
So according to your code in your second loop if (a[i] > counter)
will be true, since a[1]
is 2 and counter
is 1 in your first iteration, that leading to your last member of your array being 1 in your result.
As other people said. Don't change values before you encounter a zero. Don't assume that the end of your array is a 0. If you want to fix your problem you can set counter = a[a.length - 1];
before your second loop. But that is not very sexy, I think you can come up with another approach for your problem.
Hope this helps.
EDIT
As Robby pointed out. You will also get a problem in your first loop if you have a 1 at the beginning.
That being said, here is a version that seems to work on my side. Don't hesitate to point out any error.
public static void zeroDistance (int[] a)
{
List<Integer> zerosCoordinates = new ArrayList<>();
for (int i = 0; i < a.length; i++) {
if (a[i] == 0)
zerosCoordinates.add(i);
}
for(int i : zerosCoordinates) {
for (int j = i - 1, k = 1; j >= 0; j--, k++) {
if (a[j] == 0)
break;
if (a[j] != 0 && a[j] < k)
a[j] = k;
}
}
for (int i : zerosCoordinates) {
for (int j = i + 1, k = 1; j < a.length; j++, k++) {
if (a[j] == 0)
break;
if (a[j] != 0 && a[j] > k || j == a.length - 1)
a[j] = k;
}
}
for (int i = 0; i < a.length; i++)
System.out.print(a[i]);
}
There is surely a better way to do this. I did it in a rush sorry about that.
The problem is not only in the second loop. If the array starts with 1, results will be incorrect because of how the first loop operates.
You are right I will edit my answer :)
@RobbyCornelissen it should be good now.