Minimum pair sum operations to make array each element divisible by 4

0 0 9 minutes read

Given an array of positive integers of length n. Our task is to find minimum number of operations to convert an array so that arr[i] % 4 is zero for each i. In each operation, we can take any two elements from the array, remove both of them and put back their sum in the array.

Examples:

Input : arr = {2 , 2 , 2 , 3 , 3}
Output : 3
Explanation: In 1 operation we pick 2 and 2 and put their sum back to the array , In 2 operation we pick 3 and 3 and do same for that ,now in 3 operation we pick 6 and 2 so overall 3 operation are required.

Input: arr = {4, 2, 2, 6, 6}
Output: 2
Explanation: In operation 1, we can take 2 and 2 and put back their sum i.e. 4. In operation 2, we can take 6 and 6 and put back their sum i.e. 12. And array becomes {4, 4, 12}.

Approach : Assume the count of elements leaving remainder 1, 2, 3 when divided by 4 are brr[1], brr[2] and brr[3].

If (brr[1] + 2 * brr[2] + 3 * brr[3]) is not a multiple of 4, solution does not exist.
Now greedily pair elements of brr[2] with brr[2] and elements of brr[1] with brr[3]. This helps us to achieve fixing a maximum of 2 elements at a time. Now, we can either we left with only 1 brr[2] element or none. If we are left with 1 brr[2] element, then we can pair with 2 remaining brr[1] or brr[3] elements. This will incur a total of 2 operations.
At last, we would be only left with brr[1] or brr[3] elements (if possible). This can only we fixed in one way. That is taking 4 of them and fixing them all together in 3 operations. Thus, we are able to fix all the elements of the array.

Below is the implementation:

C++

// CPP program to find Minimum number
// of operations to convert an array 
// so that arr[i] % 4 is zero.
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum operations.
int minimumOperations(int arr[], int n)
{   
    // Counting of all the elements
    // leaving remainder 1, 2, 3 when
    // divided by 4 in the array brr.
    // at positions 1, 2 and 3 respectively.
    int brr[] = { 0, 0, 0, 0 };
    for (int i = 0; i < n; i++)
        brr[arr[i] % 4]++;
 
    // If it is possible to convert the 
    // array so that arr[i] % 4 is zero.
    if ((brr[1] + 2 * brr[2] + 3 * brr[3]) % 4 == 0) 
    {
        // Pairing the elements of brr3 and brr1.
        int min_opr = min(brr[3], brr[1]);
        brr[3] -= min_opr;
        brr[1] -= min_opr;
 
        // Pairing the brr2 elements.
        min_opr += brr[2] / 2;
 
        // Assigning the remaining brr2 elements.
        brr[2] %= 2;
 
        // If we are left with one brr2 element.
        if (brr[2]) {
 
            // Here we need only two operations
            // to convert the remaining one
            // brr2 element to convert it.
            min_opr += 2;
 
            // Now there is no brr2 element.
            brr[2] = 0;
 
            // Remaining brr3 elements.
            if (brr[3])             
                brr[3] -= 2;            
 
            // Remaining brr1 elements.
            if (brr[1]) 
                brr[1] -= 2;            
        }
 
        // If we are left with brr1 and brr2
        // elements then, we have to take four
        // of them and fixing them all together
        // in 3 operations.
        if (brr[1])        
            min_opr += (brr[1] / 4) * 3;        
        if (brr[3])        
            min_opr += (brr[3] / 4) * 3;        
 
        // Returns the minimum operations.
        return min_opr;
    }
 
    // If it is not possible to convert the array.
    return -1;    
}
 
// Driver function
int main()
{
    int arr[] = { 1, 2, 3, 1, 2, 3, 8 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << minimumOperations(arr, n);
}

Java

// Java program to find Minimum number
// of operations to convert an array 
// so that arr[i] % 4 is zero.
 
class GFG {
  
// Function to find minimum operations.
static int minimumOperations(int arr[], int n)
{   
 
    // Counting of all the elements
    // leaving remainder 1, 2, 3 when
    // divided by 4 in the array brr.
    // at positions 1, 2 and 3 respectively.
    int brr[] = { 0, 0, 0, 0 };
    for (int i = 0; i < n; i++)
        brr[arr[i] % 4]++;
  
    // If it is possible to convert the 
    // array so that arr[i] % 4 is zero.
    if ((brr[1] + 2 * brr[2] + 3 * brr[3]) % 4 == 0) 
    {
        // Pairing the elements of brr3 and brr1.
        int min_opr = Math.min(brr[3], brr[1]);
        brr[3] -= min_opr;
        brr[1] -= min_opr;
  
        // Pairing the brr2 elements.
        min_opr += brr[2] / 2;
  
        // Assigning the remaining brr2 elements.
        brr[2] %= 2;
  
        // If we are left with one brr2 element.
        if (brr[2] == 1) {
  
            // Here we need only two operations
            // to convert the remaining one
            // brr2 element to convert it.
            min_opr += 2;
  
            // Now there is no brr2 element.
            brr[2] = 0;
  
            // Remaining brr3 elements.
            if (brr[3] == 1)             
                brr[3] -= 2;            
  
            // Remaining brr1 elements.
            if (brr[1]== 1) 
                brr[1] -= 2;            
        }
  
        // If we are left with brr1 and brr2
        // elements then, we have to take four
        // of them and fixing them all together
        // in 3 operations.
        if (brr[1] != 0)        
            min_opr += (brr[1] / 4) * 3;        
        if (brr[3] != 0)        
            min_opr += (brr[3] / 4) * 3;        
  
        // Returns the minimum operations.
        return min_opr;
    }
  
    // If it is not possible to convert the array.
    return -1;    
}
  
// Driver function
public static void main(String[] args)
{
    int arr[] = { 1, 2, 3, 1, 2, 3, 8 };
    int n = arr.length;
    System.out.println(minimumOperations(arr, n));
}
}
 
// This code is contributed by Prerna Saini.

Python3

# Python program to
# find Minimum number
# of operations to
# convert an array 
# so that arr[i] % 4 is zero.
 
# Function to find
# minimum operations.
def minimumOperations(arr,n):
 
    # Counting of all the elements
    # leaving remainder 1, 2, 3 when
    # divided by 4 in the array brr.
    # at positions 1, 2 and 3 respectively.
    brr = [ 0, 0, 0, 0 ]
    for i in range(n):
        brr[arr[i] % 4]+=1;
  
    # If it is possible to convert the 
    # array so that arr[i] % 4 is zero.
    if ((brr[1] + 2 * brr[2] + 3 * brr[3]) % 4 == 0): 
     
        # Pairing the elements
        # of brr3 and brr1.
        min_opr = min(brr[3], brr[1])
        brr[3] -= min_opr
        brr[1] -= min_opr
  
        # Pairing the brr2 elements.
        min_opr += brr[2] // 2
  
        # Assigning the remaining
        # brr2 elements.
        brr[2] %= 2
  
        # If we are left with
        # one brr2 element.
        if (brr[2]):
  
            # Here we need only two operations
            # to convert the remaining one
            # brr2 element to convert it.
            min_opr += 2
  
            # Now there is no brr2 element.
            brr[2] = 0
  
            # Remaining brr3 elements.
            if (brr[3]):             
                brr[3] -= 2           
  
            # Remaining brr1 elements.
            if (brr[1]): 
                brr[1] -= 2           
         
  
        # If we are left with brr1 and brr2
        # elements then, we have to take four
        # of them and fixing them all together
        # in 3 operations.
        if (brr[1]):        
            min_opr += (brr[1] // 4) * 3       
        if (brr[3]):        
            min_opr += (brr[3] // 4) * 3       
  
        # Returns the minimum operations.
        return min_opr
 
    # If it is not possible to convert the array.
    return -1   
 
# Driver function
 
arr = [ 1, 2, 3, 1, 2, 3, 8 ]
n =len(arr)
 
print(minimumOperations(arr, n))
 
# This code is contributed
# by Anant Agarwal.

C#

// C# program to find Minimum number
// of operations to convert an array 
// so that arr[i] % 4 is zero.
using System;
 
class GFG {
 
    // Function to find minimum operations.
    static int minimumOperations(int []arr, int n)
    { 
     
        // Counting of all the elements
        // leaving remainder 1, 2, 3 when
        // divided by 4 in the array brr.
        // at positions 1, 2 and 3 respectively.
        int []brr = { 0, 0, 0, 0 };
        for (int i = 0; i < n; i++)
            brr[arr[i] % 4]++;
     
        // If it is possible to convert the 
        // array so that arr[i] % 4 is zero.
        if ((brr[1] + 2 * brr[2] + 3 * brr[3]) % 4 == 0) 
        {
            // Pairing the elements of brr3 and brr1.
            int min_opr = Math.Min(brr[3], brr[1]);
            brr[3] -= min_opr;
            brr[1] -= min_opr;
     
            // Pairing the brr2 elements.
            min_opr += brr[2] / 2;
     
            // Assigning the remaining brr2 elements.
            brr[2] %= 2;
     
            // If we are left with one brr2 element.
            if (brr[2] == 1) {
     
                // Here we need only two operations
                // to convert the remaining one
                // brr2 element to convert it.
                min_opr += 2;
     
                // Now there is no brr2 element.
                brr[2] = 0;
     
                // Remaining brr3 elements.
                if (brr[3] == 1)             
                    brr[3] -= 2;         
     
                // Remaining brr1 elements.
                if (brr[1]== 1) 
                    brr[1] -= 2;         
            }
     
            // If we are left with brr1 and brr2
            // elements then, we have to take four
            // of them and fixing them all together
            // in 3 operations.
            if (brr[1] == 1)     
                min_opr += (brr[1] / 4) * 3;     
            if (brr[3] == 1)     
                min_opr += (brr[3] / 4) * 3;     
     
            // Returns the minimum operations.
            return min_opr;
        }
     
        // If it is not possible to convert the array.
        return -1; 
    }
     
    // Driver function
    public static void Main()
    {
        int []arr = { 1, 2, 3, 1, 2, 3, 8 };
        int n = arr.Length;
        Console.WriteLine(minimumOperations(arr, n));
    }
}
 
// This code is contributed by  vt_m

PHP

<?php
// PHP program to find 
// Minimum number of 
// operations to convert 
// an array so that 
// arr[i] % 4 is zero.
 
// Function to find 
// minimum operations.
function minimumOperations($arr, $n)
{ 
    // Counting of all the 
    // elements leaving remainder
    // 1, 2, 3 when divided by 4 
    // in the array brr at positions
    // 1, 2 and 3 respectively.
    $brr = array(0, 0, 0, 0);
    for ($i = 0; $i < $n; $i++)
        $brr[$arr[$i] % 4]++;
 
    // If it is possible to 
    // convert the array so 
    // that arr[i] % 4 is zero.
    if (($brr[1] + 2 * 
         $brr[2] + 3 * 
         $brr[3]) % 4 == 0) 
    {
        // Pairing the elements 
        // of brr3 and brr1.
        $min_opr = min($brr[3], 
                       $brr[1]);
        $brr[3] -= $min_opr;
        $brr[1] -= $min_opr;
 
        // Pairing the
        // brr2 elements.
        $min_opr += $brr[2] / 2;
 
        // Assigning the remaining
        // brr2 elements.
        $brr[2] %= 2;
 
        // If we are left with 
        // one brr2 element.
        if ($brr[2]) 
        {
 
            // Here we need only two 
            // operations to convert 
            // the remaining one brr2
            // element to convert it.
            $min_opr += 2;
 
            // Now there is no 
            // brr2 element.
            $brr[2] = 0;
 
            // Remaining brr3 elements.
            if ($brr[3])             
                $brr[3] -= 2;         
 
            // Remaining brr1 elements.
            if ($brr[1]) 
                $brr[1] -= 2;         
        }
 
        // If we are left with brr1 
        // and brr2 elements then, 
        // we have to take four of 
        // them and fixing them all 
        // together in 3 operations.
        if ($brr[1])     
            $min_opr += ($brr[1] / 4) * 3;     
        if ($brr[3])     
            $min_opr += ($brr[3] / 4) * 3;     
 
        // Returns the
        // minimum operations.
        return $min_opr;
    }
     
    // If it is not possible 
    // to convert the array.
    return -1; 
}
 
// Driver Code
$arr = array(1, 2, 3, 
             1, 2, 3, 8);
$n = count($arr);
echo (minimumOperations($arr, $n));
 
// This code is contributed by 
// Manish Shaw(manishshaw1)
?>

Javascript

<script>
// Java Script program to find Minimum number
// of operations to convert an array 
// so that arr[i] % 4 is zero.
 
 
  
// Function to find minimum operations.
function minimumOperations(arr,n)
{   
 
    // Counting of all the elements
    // leaving remainder 1, 2, 3 when
    // divided by 4 in the array brr.
    // at positions 1, 2 and 3 respectively.
    let brr = [0, 0, 0, 0 ];
    for (let i = 0; i < n; i++)
        brr[arr[i] % 4]++;
  
    // If it is possible to convert the 
    // array so that arr[i] % 4 is zero.
    if ((brr[1] + 2 * brr[2] + 3 * brr[3]) % 4 == 0) 
    {
        // Pairing the elements of brr3 and brr1.
        let min_opr = Math.min(brr[3], brr[1]);
        brr[3] -= min_opr;
        brr[1] -= min_opr;
  
        // Pairing the brr2 elements.
        min_opr += brr[2] / 2;
  
        // Assigning the remaining brr2 elements.
        brr[2] %= 2;
  
        // If we are left with one brr2 element.
        if (brr[2] == 1) {
  
            // Here we need only two operations
            // to convert the remaining one
            // brr2 element to convert it.
            min_opr += 2;
  
            // Now there is no brr2 element.
            brr[2] = 0;
  
            // Remaining brr3 elements.
            if (brr[3] == 1)             
                brr[3] -= 2;            
  
            // Remaining brr1 elements.
            if (brr[1]== 1) 
                brr[1] -= 2;            
        }
  
        // If we are left with brr1 and brr2
        // elements then, we have to take four
        // of them and fixing them all together
        // in 3 operations.
        if (brr[1] == 1)        
            min_opr += (brr[1] / 4) * 3;        
        if (brr[3] == 1)        
            min_opr += (brr[3] / 4) * 3;        
  
        // Returns the minimum operations.
        return min_opr;
    }
  
    // If it is not possible to convert the array.
    return -1;    
}
  
// Driver function
 
    let arr= [1, 2, 3, 1, 2, 3, 8 ];
    let n = arr.length;
    document.write(minimumOperations(arr, n));
 
// This code is contributed by Bobby
</script>

Output

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!