BLOCK MOVE

Last Updated on March 28, 2022 by Ria Pathak

CONCEPTS USED:

Greedy algorithm.

DIFFICULTY LEVEL:

Easy.

PROBLEM STATEMENT(SIMPLIFIED):

You are given N blocks and the ith block is at position A[i]. Your task is to move every block to one single position. For that you can perform any of the two moves any number of times(possibly zero) on any block:

1. Move the ith block by 2 units to the left or to the right with a cost of 0.
2. Move the ith block by 1 unit to the left or to the right with a cost of 1. It is possible that there is more than one block at the same position initially.

See original problem statement here

For Example :

2
6
1 3 3 6 4 8
5
9 2 1 7 8

3
2

In the first test case,
1. Block at position 
1 will move to 3 at no cost.
2. Block at position 4 will move to 3 with a cost of 1.
3. Block at position 6 will move to 4 with no cost, and then move to 3 with a cost of 1.
4. Block at position 8 will move to 6, then to 4 with no cost, and from 4 to 3 with a cost of 1.
So total cost = 3.

OBSERVATION:

Have you noticed that to move from an even position to another even position or to move from an odd position to another odd position incurs no cost?

SOLVING APPROACH:

To get the minimum cost, choosing any odd position if the maximum number of given positions is odd or choosing any even position if the maximum number of given positions is even incurs the least cost because –

moving the block from odd position to another odd position or from even to another even takes 0 cost .

Amount is spend only when we move from even to odd or odd to even.

Count the number of odds i.e. the number of blocks at odd positions initially .
Also count the number of evens.
The greater of the two will the desired chosen final position!

SOLUTIONS:

#include <stdio.h>

    int main()
    {
    //write your code here
    int t;scanf("%d",&t);
     while(t--)
    {
    int n;scanf("%d",&n);
    int a[n],odd=0,even=0;
    for(int i=0;i<n;i++)
    {
      scanf("%d",&a[i]);
      if(a[i]%2)
      odd++;
      else
      even++;
    }
    int mx=even>odd?even:odd;
    int ans=0;
    for(int i=0;i<n;i++)
    {
      if(mx==odd)
      {
        if(a[i]%2==0)
        ans++;
      }
      else
      {
        if(a[i]%2)
        ans++;
      }
    }
    printf("%d\n",ans);
    }
     return 0;
    }

 #include <bits/stdc++.h>
    using namespace std;

     int main()
    {
    //write your code here
     int t;cin>>t;
     while(t--)
    {
    int n;cin>>n;
    int a[n],odd=0,even=0;
    for(int i=0;i<n;i++)
    {
      cin>>a[i];
      if(a[i]%2)
      odd++;
      else
      even++;
    }
    int mx=max(even,odd);
    int ans=0;
    for(int i=0;i<n;i++)
    {
      if(mx==odd)
      {
        if(a[i]%2==0)
        ans++;
      }
      else
      {
        if(a[i]%2)
        ans++;
      }
    }
    cout<<ans<<"\n";
    }
     return 0;
    }

import java.util.*;
    import java.io.*;

    class block {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int t= sc.nextInt();
        while(t-- >0 ){
            int n = sc.nextInt();
            int odd=0,even=0;
            int a[]=new int[n];
            for(int i=0;i<n;i++)
            {
                a[i] = sc.nextInt();
                if(a[i]%2==1)
                odd++;
                else
                even++;
            }
            int max=odd>even?odd:even;
            int ans=0;
            for(int i=0;i<n;i++){
              if(max==odd)
      {
        if(a[i]%2==0)
        ans++;
      }
      else
      {
        if(a[i]%2==1)
        ans++;
      }
                }
                System.out.println(ans);

        }
    }
    }

# your code goes here
for _ in range(int(input())):
	
	n = int(input())
	a = list(map(int,input().split()))
	odd, even = 0, 0
	
	for i in range(n):
	
		if a[i] % 2:
			odd += 1
	
		else:
			even += 1
	
	mx = max(even, odd)
	ans = 0
	
	for i in range(n):
	
		if mx == odd:
	
			if a[i] % 2 == 0:
				ans += 1
	
		else:
	
			if a[i] % 2:
				ans += 1
	
	print(ans)

[forminator_quiz id="1402"]

This article tried to discuss Greedy algorithm. Hope this blog helps you understand and solve the problem. To practice more problems on Greedy algorithm you can check out MYCODE | Competitive Programming.