I guess u got confused with the comment I wrote, I have added 2 print
statements and now I guess it should be clear to you as to why the code is
O(n). The comment means that each element of the min_steps_dp will be
ACCESSED only ONCE over the execution of the entire program. Hence the outer
loop still remains O(n). The next_vacat variable if u notice is always
incremental, never reset to a previous value.
#include<stdio.h>
#include<stdlib.h>
#define MAX 0x7fffffff
inline int min(int a, int b) {
return a >= b ? b : a;
}
int find_min_steps(int const * const input, const int n) {
int min_steps_dp[n], i, temp, next_vacant;
for (i = 0; i < n; min_steps_dp[i++] = MAX);
min_steps_dp[0] = 0;
next_vacant = 1; // Is the index in the array whose min_steps needs to be
updated
// in the next iteration.
for (i = 0; i < n && min_steps_dp[n - 1] == MAX; i++) {
temp = i + input[i];
if (temp >= n) {
min_steps_dp[n - 1] = min(min_steps_dp[n - 1], min_steps_dp[i] + 1);
temp = n - 1;
} else {
printf("Updating min[%d] to %d \n", i + input[i], min_steps_dp[i] +
1);
min_steps_dp[temp] = min(min_steps_dp[temp], min_steps_dp[i] + 1);
}
if (temp > next_vacant) {
printf("i: %d \n", i);
for (; next_vacant < temp; next_vacant++) {
printf("next_vacant: %d \n", next_vacant);
min_steps_dp[next_vacant]
= min(min_steps_dp[temp], min_steps_dp[next_vacant]);
}
}
}
for (i=0;i<n;printf("%d ",min_steps_dp[i++]));printf("\n");
return min_steps_dp[n-1];
}
int main() {
int n, *input, i;
scanf("%d",&n);
if ((input = (int *)malloc(n * sizeof(int))) == NULL) {
return -1;
}
for (i = 0;i < n; scanf("%d",&input[i++]));
printf("Minimum steps: %d\n",find_min_steps(input, n));
return 0;
}
Programmers should realize their critical importance and responsibility in a
world gone digital. They are in many ways similar to the priests and monks
of Europe's Dark Ages; they are the only ones with the training and insight
to read and interpret the "scripture" of this age.
On Fri, Jan 14, 2011 at 1:49 PM, Decipher <[email protected]> wrote:
> I don't think the inner loop is executing only once . Kindly check it for
> this test case {1,3,5,8,9,2,6,7,6,8,9} . And try to print i in inner loop
> you will find that for same values of i(Outer index) inner loop is called.
> Its an O(n2) solution .
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
