Even numbers before odd numbers using array and only one loop

Question

I attempted the problem. I am not getting the right solution. Kindly help.

Problem : Return an array that contains the exact same numbers as the given array, but rearranged so that all the even numbers come before all the odd numbers. Other than that, the numbers can be in any order. You may modify and return the given array, or make a new array.
evenOdd([1, 0, 1, 0, 0, 1, 1]) → [0, 0, 0, 1, 1, 1, 1]
evenOdd([3, 3, 2]) → [2, 3, 3]
evenOdd([2, 2, 2]) → [2, 2, 2]

public int[] evenOdd(int[] nums) {
  
  int l = nums.length;
  
  if(l<2)
  return nums;
  
  int j=l-1;
  for(int i=0;i<l;i++)
  {
    if(nums[i]%2==1)
    {
      while(j>i && nums[j]%2!=0) {
          j--;
      }         
      int t=nums[i];
      nums[i]=nums[j];
      nums[j]=t;
       
      j--;           
    }  
  }   
  return nums;
}

In your example you're using 2 loops (for and while) and you state in your title that you must use only one loop ?.. So what do you need ? — arso
– arso, Commented Oct 4, 2016 at 13:23
@Abhishek Sharma: Please have a look at my O(N) time and O(1) space complexity solution... — User_Targaryen
– User_Targaryen, Commented Oct 5, 2016 at 6:28
This is basically the partition algorithm of quicksort. You just need to apply the partition just once. — Klitos Kyriacou
– Klitos Kyriacou, Commented Oct 5, 2016 at 7:04

Shaishav Jogani · Accepted Answer · 2016-10-05 06:06:16Z

2

As order of array doesn't matter and you need only one loop, you can try below function,

public int[] evenOdd(int[] nums) {
    if (nums.length < 2) return nums;

    int[] result = new int[nums.length];
    int even = 0;
    int odd = nums.length - 1;

    for (int i = 0; i < nums.length; i++) {
        if (nums[i] % 2 == 0)
            result[even++] = nums[i];
        else
            result[odd--] = nums[i];
    }
    return result;
}

edited Oct 5, 2016 at 6:06

answered Oct 4, 2016 at 13:43

Shaishav Jogani

2,1193 gold badges25 silver badges33 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Abhishek Sharma Over a year ago

Thanks a lot Shaishav!

aquinas · Accepted Answer · 2016-10-04 13:10:29Z

2

You're actually super close. If you just wrap this code that you have:

int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
j--;

inside of an if

if (j > i)

your code actually works.

answered Oct 4, 2016 at 13:10

aquinas

23.9k5 gold badges60 silver badges82 bronze badges

1 Comment

Abhishek Sharma Over a year ago

Thanks aquinas. Could you tell if this problem can be solved using only one loop?

raphael75 · Accepted Answer · 2016-10-04 12:17:22Z

1

Not sure if this is "cheating", but you could create 2 arrays, 1 to hold the evens and 1 to hold the odds. In your loop, you would copy all the numbers of each value to their even or odd array, and then after the loop, join/merge the arrays together in a new array and return the new array.

answered Oct 4, 2016 at 12:17

raphael75

3,2686 gold badges35 silver badges49 bronze badges

1 Comment

aquinas Over a year ago

That works but you are tripling the amount of memory required.

xehpuk · Accepted Answer · 2016-10-04 14:12:23Z

1

If performance is not too important, you could use a stream:

static int[] evenOdd(int[] nums) {
    return Arrays.stream(nums)
            .boxed()
            .sorted(Comparator.comparingInt(i -> i % 2))
            .mapToInt(i -> i)
            .toArray();
}

Unfortunately, IntStream doesn't have a sorted method that takes a Comparator (only a parameterless method, that's why you have to box and unbox to use Stream.sorted(Comparator).

answered Oct 4, 2016 at 14:12

xehpuk

8,3904 gold badges37 silver badges61 bronze badges

Comments

User_Targaryen · Accepted Answer · 2016-10-05 06:26:44Z

Here is a code that takes O(N) time and O(1) space to accomplish your task. I apologise for the Python code.

arr = list(map(int, raw_input().split()))

i = 0
j = len(arr) - 1

while i<j:
    if arr[i]%2 != 0 and arr[j]%2 == 0:
        t = arr[i]
        arr[i] = arr[j]
        arr[j] = t
        i = i + 1
        j = j -1

    elif arr[i]%2 == 0 and arr[j]%2 == 0:
        i = i + 1

    elif arr[i]%2 == 0 and arr[j]%2 != 0:
        j = j - 1

    else:
        j = j - 1

print arr

Explanation: The code logic is quite self explanatory. We have two counters, i starting from left end and j starting from right end. If the left counter is pointing to an even then we just increment it, as it is in its correct place. [Remember you want to shift evens to the left. So this even is already in the left side of the array.So we just increment i]. Please look at the code logic to find out what actions are taken based on the current pointers on an even or an odd element.

For example:

If we find i pointing to an odd and j pointing to an `even, then we swap and move both pointers. This is understandable, I hope

The above solution is in-place and takes O(1) space and O(N) time... Hope this helps!!

Collectives™ on Stack Overflow

Even numbers before odd numbers using array and only one loop

5 Answers 5

1 Comment

1 Comment

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

1 Comment

1 Comment

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related