Java > Array-3 > fix45 (CodingBat Solution)

Problem:

(This is a slightly harder version of the fix34 problem.) 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}


Solution:

public int[] fix45(int[] nums) {
  for (int i = 0; i < nums.length; i++) {
    if (nums[i] == 4) {
      for (int j = 0; j < nums.length; j++) {
        if (nums[j] == 5) {
          if (j > 0 && nums[j-1] != 4) {
            int tmp = nums[i+1];
            nums[i+1] = 5;
            nums[j] = tmp;
          } 
          else if (j == 0) {
            int tmp = nums[i+1];
            nums[i+1] = 5;
            nums[j] = tmp;
          }
                     
        }
      }
    }
  }
  return nums;
}

13 comments:

  1. UnknownFebruary 17, 2015 at 11:29 AM

    Better optimized code with complexity less than n^2. need not search the entire array again and again for 5. just break when you find the first 5 . when looping again start from the point where you found the first 5.

    public int[] fix45(int[] nums) {
    int index=0;
    for(int i=0;i<=nums.length-2;i++){
    if(nums[i]==4 &&nums[i+1]!=5){
    for(int j=index;j<=nums.length-1;j++){
    if(nums[j]==5 && j==0){
    nums[0]=nums[i+1];
    nums[i+1]=5;
    index++;
    }
    if(nums[j]==5 && nums[j-1]!=4){
    nums[j]=nums[i+1];
    nums[i+1]=5;
    index=j;
    break;
    }
    }
    }

    }
    return nums;
    }

    ReplyDelete
  2. UnknownFebruary 17, 2015 at 11:45 AM

    Better optimized code with complexity less than n^2. need not search the entire array again and again for 5. just break when you find the first 5 . when looping again start from the point where you found the first 5.

    public int[] fix45(int[] nums) {
    int index=0;
    for(int i=0;i<=nums.length-2;i++){
    if(nums[i]==4 &&nums[i+1]!=5){
    for(int j=index;j<=nums.length-1;j++){
    if(nums[j]==5 && j==0){
    nums[0]=nums[i+1];
    nums[i+1]=5;
    index++;
    }
    if(nums[j]==5 && nums[j-1]!=4){
    nums[j]=nums[i+1];
    nums[i+1]=5;
    index=j;
    break;
    }
    }
    }

    }
    return nums;
    }

    ReplyDelete
    Replies
    1. KasparMay 30, 2015 at 3:14 PM

      Hey:) Here's a clearer version, you don't need index at all. This is your solution - all credit goes to you:

      public int[] fix45(int[] nums) {
      for(int i=0;i<nums.length-1;i++){
      if(nums[i]==4 &&nums[i+1]!=5){
      for(int j=0;j<nums.length;j++){
      if(nums[j]==5 && j==0){
      nums[0]=nums[i+1];
      nums[i+1]=5;
      }
      if(nums[j]==5 && nums[j-1]!=4){
      nums[j]=nums[i+1];
      nums[i+1]=5;
      break;
      }
      }
      }
      }
      return nums;
      }

      Delete
    2. KasparMay 30, 2015 at 3:16 PM

      Here is even more clear(don't need break)
      public int[] fix45(int[] nums) {
      for(int i=0;i<nums.length-1;i++){
      if(nums[i]==4 &&nums[i+1]!=5){
      for(int j=0;j<nums.length;j++){
      if(nums[j]==5 && j==0){
      nums[0]=nums[i+1];
      nums[i+1]=5;
      }
      if(nums[j]==5 && nums[j-1]!=4){
      nums[j]=nums[i+1];
      nums[i+1]=5;
      }
      }
      }
      }
      return nums;
      }

      Delete
    3. KasparMay 30, 2015 at 3:23 PM

      Here is even more clear(don't need break)
      public int[] fix45(int[] nums) {
      for(int i=0;i<nums.length-1;i++){
      if(nums[i]==4 &&nums[i+1]!=5){
      for(int j=0;j<nums.length;j++){
      if(nums[j]==5 && j==0){
      nums[0]=nums[i+1];
      nums[i+1]=5;
      }
      if(nums[j]==5 && nums[j-1]!=4){
      nums[j]=nums[i+1];
      nums[i+1]=5;
      }
      }
      }
      }
      return nums;
      }

      Delete
    4. KasparMay 30, 2015 at 3:24 PM

      Hey:) Here's a clearer version, you don't need index at all. This is your solution - all credit goes to you:

      public int[] fix45(int[] nums) {
      for(int i=0;i<nums.length-1;i++){
      if(nums[i]==4 &&nums[i+1]!=5){
      for(int j=0;j<nums.length;j++){
      if(nums[j]==5 && j==0){
      nums[0]=nums[i+1];
      nums[i+1]=5;
      }
      if(nums[j]==5 && nums[j-1]!=4){
      nums[j]=nums[i+1];
      nums[i+1]=5;
      break;
      }
      }
      }
      }
      return nums;
      }

      Delete
  3. AnonymousFebruary 28, 2016 at 5:02 PM

    This is what I came up with:

    public int[] fix45(int[] nums) {
    int len = nums.length;
    int temp;
    for (int i = 0; i < len - 1; i++) {
    if (nums[i] == 4 && nums[i + 1] != 5) {
    for (int j = len - 1; j >= 0; j--) {
    if (nums[j] == 5) {
    if (j - 1 >= 0 && nums[j - 1] != 4 || j == 0) {
    temp = nums[i + 1];
    nums[i + 1] = nums[j];
    nums[j] = temp;
    }
    }
    }
    }
    }
    return nums;
    }

    ReplyDelete
  4. AnonymousOctober 4, 2016 at 8:50 AM

    Can't say that it's better than what was already suggested, but here you go anyway.

    public int[] fix45(int[] nums) {
    int temp = 0;
    for (int i=0; i0 && nums[x]==5 && nums[x-1]!=4))
    {
    nums[x]=nums[i+1];
    nums[i+1]=5;
    break;
    }
    }

    }
    return nums;
    }


    ReplyDelete
  5. nh2March 13, 2017 at 11:55 AM

    public int[] fix45(int[] nums) {
    int pos5 = 0; // will hold the position of the next 5
    for (int i=0 ; i0 && nums[pos5-1]==4) // search for the next 5
    pos5++;
    nums[pos5++]=nums[++i];
    nums[i]=5;
    }
    return nums;
    }

    ReplyDelete
    Replies
    1. nh2March 13, 2017 at 12:16 PM

      public int[] fix45(int[] nums) {
      int pos5 = 0; // will hold the position of the next 5
      for (int i=0 ; i < nums.length-1 ; ++i)
      if (nums[i] == 4 && nums[i+1] != 5){
      while (nums[pos5] != 5 || pos5 > 0 && nums[pos5-1] == 4) // search for the next 5
      pos5++;
      nums[pos5++] = nums[++i];
      nums[i] = 5;
      }
      return nums;
      }

      Delete
  6. AnonymousSeptember 16, 2017 at 1:26 AM

    Easy and clever technique!!!

    public int[] fix45(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
    for (int j = 0; j < nums.length; j++) {
    if (nums[i] == 5 && nums[j] == 4) {
    int t = 0;
    t = nums[j + 1];
    nums[j + 1] = nums[i];
    nums[i] = t;
    }

    }
    }
    return nums;
    }

    ReplyDelete
  7. UnknownJuly 25, 2020 at 3:03 PM

    public int[] fix45(int[] nums) {
    //Fast Solution//
    int pos = 0;
    boolean found = false;
    for (int i = 0; i < nums.length - 1; i++)
    {
    if (nums[i] == 4)
    {
    for (int j = pos; j < nums.length && !found; j++)
    {
    if (nums[j] == 5 && (j == 0 || nums[j - 1] != 4))
    {
    nums[j] = nums[i + 1];
    nums[i + 1] = 5;
    found = true;
    pos = j;
    }
    }
    }
    found = false;
    }
    return nums;
    }

    ReplyDelete
  8. UnknownSeptember 29, 2021 at 9:18 PM

    public int[] fix45(int[] nums) {

    int l=nums.length;
    int[] ar=new int[l];

    for (int i=0; i<l ; i++){
    if (nums[i]==4) {
    ar[i]=4;
    ar[i+1]=5;
    }
    }

    for (int i=0; i<l ; i++){
    if (nums[i]!=4 && nums[i]!=5){
    for (int j=0; j<l ; j++){
    if (ar[j]!=4 && ar[j]!=5) ar[j]=nums[i];
    }
    }

    }

    return ar;
    }

    ReplyDelete