DP after a long time :)

At work it seems I will be shifting from Java to C++ now. I have never coded in C++ before, whenever I have it was solely for the purpose to use their beautiful vector, map, string and all libraries. So I guess I should start doing some C++ coding too. A step towards it, I wrote a C code after a looong time. Obviously, a DP problem to target :D. It is a typical interview problem, just that the O(n) is also possible, and I feel it’s the best one can do.

Problem: Given an array of integers, each element represents the max number of jumps can make forward. What is the minimum number of element selections to reach the end of the array (starting from the first element).
Example: arr = 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9
Here the min # of selections is : 3
with the sequence : 1-> 3 -> 8 ->9
First element is 1, so can only go to 3.
Second element is 3, so can make at most 3 jumps: eg to 5 or 8 or 9.
If an element is 0, then cannot make any jumps

PS: Have not checked for corner cases. Laziness again 😛

#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) {
      for (; next_vacant < temp; 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;
}

Another Greedy solution provided by Abhishek in O(n) time and O(1) space.

#include <iostream>
#include <vector>

using namespace std;

int find_min_steps(vector<int>& input) {
   int start, end, next_start;
   vector<int> result;
   start = end = 0;
   int n = input.size();

   while (end < n-1) {
     int max = -1;
     for(int w = 0; start <= end ; w++, start++){
       if(input[start] + w > max) {
         max = input[start] + w ;
         next_start = start;
       }
     }
     start = end + 1;
     end = next_start + input[next_start];
     result.push_back(input[next_start]);
   }
   cout << endl << "steps are : ";
   for(int i =0; i< result.size(); ++i)
     cout << endl << result[i];
   cout << endl;
   return result.size();
}

int main() {
  vector<int> input;
  int t = -1;
  cout << endl << "enter input values.. (-1) to end" << endl;
  do {
   cin >> t;
   input.push_back(t);
  } while(t != -1);
  input.resize(input.size() -1); //remove last pushed -1.
  cout << endl << "Minimum steps: "<< find_min_steps(input) << endl;
  return 0;
}

Advertisements

An old question

Not that it has been long since I left college, but I remember once when I was preparing for my placements, I came across an interesting problem which is:
An array {A1,A2,A3,….,An,B1,B2,……,Bn} is given and we have to rearrange it as {A1,B1,A2,B2……} .Give an algo with minimum time and space complexity

I got it here, this is an awesum forum BTW, I really liked it and definitely plan on following it soon.

I remember spending a lot of time on it and discovering a pattern in the solution. Today, I saw this problem somewhere else and I remembered to have done some investigation over it. Luckily I found the code for it which I had written then, but unfortunately, I forgot the pattern 😛 and now I am too lazy to pick up the pen and paper and start all over again. I’l post the code here, I feel it’s O(1) space and O(n) time, but looking at the level of discussion at the forum I pointed to I feel something is wrong in the code. Can you find it for me ??

Also looking at this code of mine, for the first second, I couldn’t make out any sense of it and suddenly I realized the importance of comments and clean code. 🙂

#include <stdio.h>

int main() {
  int n, i, j , k, t1, l;
  scanf("%d",&n);
  int arr[n<<1 + 1];
  for (i=1,j=n<<1,k=-1,l=0;i <= j ; i++ ) {
    if ( i <= n )
      arr[i] = k+=2; // 1 3 5 7
    else
      arr[i] = l+=2;
  }
  arr[0]=0;

  printf("\n\nBefore Shuffling ..\n");
  for (i = 0;i <= n<<1; i++) printf("%d ", arr[i]);
  printf("\n\nShuffling Now ..\n");

  // Shuffleing starts 
  i = 1;
  int chk[j+1]; // To check if each element was visited only once
  for (i=0;i<=j;i++) chk[i]=0;
  i = 1;
  while (i <= j) {
    while (i<=j && arr[i] == i) {
      chk[i]++;
      i++;
    }
    if (i >j)
      break;
    t1 = arr[i];   // swap with temp
    k = i; // note the curr. loc in array
    l = i;
    printf("%d   : Value of i entering loop\n",i);
    while (1) {
      k = k & 1 ? (k + 1) / 2 : n + k / 2;
      chk[k]++;
      if (k == i) break;
      arr[l] = arr[k];
      l = k;
    }
    arr[l] = t1;
  }
  for (i = 0;i <= j;i++) printf("%d ",arr[i]);
  printf("\n Checking which element was processed how many times.\n");
  for (i = 0; i <= j; i++)
    printf("%d  %d\n",i,chk[i]);
  return 0;
}
%d bloggers like this: