Social Icons

Saturday, April 17, 2010

fix45: Solutions for Javabat:09


This Question falls under harder array questions, here it goes

Return an array that contains exactly the same numbers as the given array, but rearranged so that every 4 is immediately followed by a 5. Do not move the 4's, but every other number may move. The array contains the same number of 4's and 5's, and every 4 has a number after it that is not a 4. In this version, 5's may appear anywhere in the original array.

fix45({5, 4, 9, 4, 9, 5}) → {9, 4, 5, 4, 5, 9}
fix45({1, 4, 1, 5}) → {1, 4, 5, 1}
fix45({1, 4, 1, 5, 5, 4, 1}) → {1, 4, 5, 1, 1, 4, 5}

Source

Here is the to-do list or rather algorithm of the solution i came up with.

  • Loop through every element of the array if it is a 4 get the index of it.
  • Check whether it has a 5 after it. if it does , we do not need to worry about it.
  • Now search for a 5 in the array which is not attached to a 4. because we would not want to alter already fixed 4 s.
  • After we found the index of a 5 swap it with the preceding element of 4.
  • We have to consider boundaries of loops so that our code won’t throw Array index out of bounds exceptions.
  1: public int[] fix45(int[] nums) {
  2:    int len=nums.length;
  3:             
  4:             for(int i=0 , j=0 ; i < len-1 ; i++){
  5:                 if(nums[i] == 4){
  6:                     if(nums[i+1]==5) continue;
  7:                     while(j<len){
  8:                         if(j==0 && nums[j]==5 ) break; 
  9:                         else if(nums[j]==5 && nums[j-1] != 4) break; 
 10:                         j++;
 11:                     }// end while
 12: 
 13:                     nums[j]=nums[i+1]; // swap values
 14:                     nums[i+1]=5;
 15:                     nums[i]=4;
 16:                     j=0;
 17:                     i++; // skip 5
 18:                 }// end if
 19: 
 20:             }// end for
 21: 
 22:           return nums;
 23: }
 
 
Blogger Templates http://slots.to/