Simplicity

How would you define an unsigned int of 32 bits (you can imagine about 64 bits) to be infinite?

some might

const unsigned int kMaxUnsignedInt = 0xFFFFFFFF;

Others (shifting lovers) may

const unsigned int kMaxUnsignedInt =  (((1<<30) - 1) << 2 ) | 3;

Few may

const unsigned int kMaxUnsignedInt = ~0;

I did

const unsigned int kMaxUnsignedInt = -1;

What would you do?

On a side note
What would the following code do?

const unsigned int kMaxUnsigndInt = (1<<31) - 1;

Zero sum sub-array

Question: There is an array consisting of postive and negative integers. find the subarray whose sum is 0.

Solution:

#include<ext/hash_map>
#include<iostream>
#include<vector>

using namespace __gnu_cxx;
using namespace std;

int main() {
  int n;
  cin >> n;
  int prefix_sum = 0;
  hash_map<int, int> find_subarray;
  int start_index = -1, end_index = -1;
  for (int i = 0, t = -1; i < n; ++i) {
    cin >> t;
    if (!t) {
      start_index = i;
      end_index = i;
      break;
    }
    prefix_sum += t;
    if (!prefix_sum) {
      start_index = 0;
      end_index = i;
      break;
    }
    if (find_subarray.find(prefix_sum) == find_subarray.end()) {
      find_subarray[prefix_sum] = i;
    } else {
      start_index = find_subarray[prefix_sum] + 1;
      end_index = i;
      break;
    }
  }
  if (start_index != -1) {
    cout << "Zero sum subarray found. Start index : " << start_index
         << ". End Index: " << end_index << "\n";
  }
  return 0;
}

Zeros and Ones .. One Pass

Have heard this question a lot and wanted to code it. I initially always used the version 1 (described below) of this code to form solutions, but I figured an optimization and the version 2 is actually a one-pass algorithm.

Version 1: ( debatable one pass)

#include <iostream>
#include <vector>

using namespace std;

int main() {
  int n;
  cin >> n;
  // containing 0s and 1s
  vector<int> binaries;
  for (int i = 0, t = -1; i < n; ++i) {
    cin >> t;
    binaries.push_back(t);
  }

  vector<int>::iterator back_iter = binaries.begin();
  vector<int>::iterator front_iter = binaries.begin();

  for (; front_iter != binaries.end(); ++front_iter) {
    if (*front_iter == 0) {
      // find the localtion of the back pointer which is pointing to a 1
      while (back_iter != front_iter && *back_iter == 0) {
        ++back_iter;
      }
      if (back_iter != front_iter) {
        // found a place to replace
        iter_swap(back_iter, front_iter);
      }
    }
  }

  for (int i = 0; i < binaries.size(); ++i) {
    cout << binaries[i] << " ";
  }
  cout << "\n";
  return 0;
}

Version 2: Definitely one – pass 🙂

#include <iostream>
#include <vector>

using namespace std;

int main() {
  int n;
  cin >> n;
  // containing 0s and 1s
  vector<int> binaries;
  for (int i = 0, t = -1; i < n; ++i) {
    cin >> t;
    binaries.push_back(t);
  }

  vector<int>::iterator front_iter = binaries.begin();
  vector<int>::iterator back_iter = binaries.end() - 1;

  for (; front_iter != binaries.end() && front_iter != back_iter; ) {
    if (*front_iter) {
      iter_swap(front_iter, back_iter);
      --back_iter;
    } else {
      ++front_iter;
    }
  }

  for (int i = 0; i < binaries.size(); ++i) {
    cout << binaries[i] << " ";
  }
  cout << "\n";
  return 0;
}

Finally I coded this. 😀

Another simple solution

Am getting lesser and lesser time to maintain this blog 😦 .. anyways a friend of mine asked me a problem to solve recently and as soon as I got time (with some outside help :D) I was able to come to a very elegant looking simple solution. Sometimes we forget the basic properties of some algorithms which surprisingly can solve classic problems.

Problem: Given an array of elements find the largest possible number that can be formed by using the elements of the array.
eg: 10 9
ans: 910
eg: 2 3 5 78
ans: 78532

Solution:

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

// Uncomment the commented code to see the behaviour

long long int NumberConcater(int a, int b) {
  char str_num[100];
  int sizea = sprintf(str_num, "%d", a);
  // cout << "1 : " << str_num;
  sprintf(str_num + sizea, "%d", b);
  // cout << "   2 : " << str_num;
  long long int option_number = atoll(str_num);
  // cout << "   Number : " << option_number << "\n";
  return option_number;
}
static bool MySorter(int a, int b) {
  long long int o1 = NumberConcater(a, b);
  long long int o2 = NumberConcater(b, a);
  return o1 > o2;
}

int main() {
  int n;
  cin >> n;
  vector<int> nums;
  for (int i = 0, t = 0; i < n; ++i) {
    cin >> t;
    nums.push_back(t);
  }
  sort(nums.begin(), nums.end(), MySorter);
  for (int i = 0; i < n; ++i) {
    cout << nums[i] << "\n";
  }
  return 0;
}

Using the concept of ordering, (I believe) this problem can be solved like this. Which is kinda cool 😀

Change

Never thought people (me for that matter) change so quickly. Not long ago I posted here about how I don’t enjoy computers much but just barely make up with them. Yesterday I had to travel to my parents and I was shocked at how badly I was bored when I was not coding. I had to stop listening to music and open a terminal and start coding. I guess when one does something everyday, it becomes difficult to hate it (arranged marriages? :P). Wanted to start on a task which I could complete so wrote the complete code for reversing all the words in a given string (ya ya … I know .. I know its too easy :D).
Re-wrote all the library functions, have to confirm their behaviour though :P. Do let me know if there are any obvious/major bugs.

#include <stdio.h>
#include <stdlib.h>

#define _DEBUG_HAULT_ scanf("%*d");
#define STR_TERM '\0'
#define MAX_INPUT_LENGTH 1000
#define DELIMITERS " ,.':;"

int my_strlen(const char* str) {
  register int len = -1;
  for (;*(str + ++len););
  return len;
}

char* my_strchr(const char* s, int ch) {
  if (NULL == s) return NULL;
  for (; STR_TERM != *s && *s != ch; ++s);
  return STR_TERM == *s ? NULL : (char *)s;
}

char* my_strrev(const char* str, register int l) {
  register int i = -1;
  char *retVal = (char *)malloc(sizeof(char) * l);
  retVal[0] = retVal[l] = STR_TERM;
  for (; l; retVal[++i] = str[--l]);
  return retVal;
}

char* my_strtok(char *buf, const char* delim) {
  static char* record;
  record = (buf == NULL) ? record : buf;
  if (*record == STR_TERM || NULL == record) return NULL;
  char* temp = record;
  while ((STR_TERM != *record) && (NULL == my_strchr(delim, *record))) {
    ++record;
  }
  if (STR_TERM == *record) return temp;
  while ((STR_TERM != *record) && (NULL != my_strchr(delim, *record))) {
    *record = STR_TERM;
    ++record;
  }
  return temp;
}

// Removes all the punctuations (marked in constant DELIMITERS) and inserts
// only 1 space between words.
int main(int argc, char *argv[]) {
  char input[MAX_INPUT_LENGTH], output[MAX_INPUT_LENGTH];
  input[0] = output[0] = STR_TERM;
  scanf("%[^\n]", input);
  register int len = 0, temp = 0;
  register char* ptr = NULL;
  for (ptr = my_strtok(input, DELIMITERS);
       ptr;
       ptr = my_strtok(NULL, DELIMITERS)) {
    temp = my_strlen(ptr);
    sprintf(output + len, "%s ", my_strrev(ptr, temp));
    len += (temp + 1);
  }
  output[len - 1] = STR_TERM;
  printf("%s\n", output);
  printf("%s\n", my_strrev(output, my_strlen(output)));
  return 0;
}

After I was done, I found out about strsep 😛

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;
}

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: