Проверьте, можно ли разделить массив из 1 и 2 на 2 части с равной суммой

Опубликовано: 14 Января, 2022

Для массива, содержащего N элементов, каждый элемент равен 1 или 2. Задача состоит в том, чтобы выяснить, можно ли разделить массив на 2 части так, чтобы сумма элементов в обеих частях была равной.
Примеры:

 Ввод: N = 3, arr [] = {1, 1, 2}
Выход: ДА

Ввод: N = 4, arr [] = {1, 2, 2,}
Выход: НЕТ

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Идея состоит в том, чтобы заметить, что массив можно разделить на две части с равной суммой только в том случае, если общая сумма массива четная, то есть делимая на 2.
Скажем, общая сумма массива обозначена суммой .
Теперь возникает два случая:

Если сумма / 2 четна : когда значение суммы / 2 также четное, это означает, что сумма каждой из двух частей также четна, и нам не нужно рассматривать что-либо особенное. Итак, верните true для этого случая.
Если сумма / 2 нечетна : Если значение суммы / 2 нечетно, это означает, что сумма каждой части также нечетная. Это возможно только тогда, когда каждая из двух частей массива содержит хотя бы одну 1. Рассмотрим случаи, когда сумма = 2, или 6, или 10. Итак, когда сумма / 2 нечетная, проверьте, есть ли хотя бы одна 1 в массиве.

Below is the implementation of the above approach:

C++

// C++ implementation of the above
// approach:
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if it is possible to
// split the array in two parts with
// equal sum
bool isSpiltPossible(int n, int a[])
{
    int sum = 0, c1 = 0;
 
    // Calculate sum of elements
    // and count of 1"s
    for (int i = 0; i < n; i++) {
        sum += a[i];
 
        if (a[i] == 1) {
            c1++;
        }
    }
 
    // If total sum is odd, return False
    if (sum % 2)
        return false;
 
    // If sum of each part is even,
    // return True
    if ((sum / 2) % 2 == 0)
        return true;
 
    // If sum of each part is even but
    // there is atleast one 1
    if (c1 > 0)
        return true;
    else
        return false;
}
 
// Driver Code
int main()
{
    int n = 3;
    int a[] = { 1, 1, 2 };
 
    if (isSpiltPossible(n, a))
        cout << "YES";
    else
        cout << "NO";
 
    return 0;
}

Java

// Java implementation of the above
// approach:
class GFG
{
     
// Function to check if it is possible
// to split the array in two parts with
// equal sum
static boolean isSpiltPossible(int n,
                               int a[])
{
    int sum = 0, c1 = 0;
 
    // Calculate sum of elements
    // and count of 1"s
    for (int i = 0; i < n; i++)
    {
        sum += a[i];
 
        if (a[i] == 1)
        {
            c1++;
        }
    }
 
    // If total sum is odd, return False
    if(sum % 2 != 0)
        return false;
 
    // If sum of each part is even,
    // return True
    if ((sum / 2) % 2 == 0)
        return true;
 
    // If sum of each part is even but
    // there is atleast one 1
    if (c1 > 0)
        return true;
    else
        return false;
}
 
// Driver Code
public static void main(String[] args)
{
    int n = 3;
    int a[] = { 1, 1, 2 };
 
    if (isSpiltPossible(n, a))
        System.out.println("YES");
    else
        System.out.println("NO");
}
}
 
// This code is contributed by
// Code Mech

Python3

# Python3 implementation of the above
# approach:
 
# Function to check if it is possible
# to split the array in two halfs with
# equal Sum
def isSpiltPossible(n, a):
 
    Sum = 0
    c1 = 0
 
    # Calculate Sum of elements
    # and count of 1"s
    for i in range(n):
        Sum += a[i]
 
        if (a[i] == 1):
            c1 += 1
 
    # If total Sum is odd, return False
    if (Sum % 2):
        return False
 
    # If Sum of each half is even,
    # return True
    if ((Sum // 2) % 2 == 0):
        return True
 
    # If Sum of each half is even
    # but there is atleast one 1
    if (c1 > 0):
        return True
    else:
        return False
 
# Driver Code
n = 3
a = [ 1, 1, 2 ]
 
if (isSpiltPossible(n, a)):
    print("YES")
else:
    print("NO")
 
# This code is contributed
# by Mohit Kumar

C#

// C# implementation of the above
// approach:
using System;
 
class GFG
{
     
// Function to check if it is possible
// to split the array in two parts with
// equal sum
static bool isSpiltPossible(int n,
                            int[] a)
{
    int sum = 0, c1 = 0;
 
    // Calculate sum of elements
    // and count of 1"s
    for (int i = 0; i < n; i++)
    {
        sum += a[i];
 
        if (a[i] == 1)
        {
            c1++;
        }
    }
 
    // If total sum is odd, return False
    if(sum % 2 != 0)
        return false;
 
    // If sum of each part is even,
    // return True
    if ((sum / 2) % 2 == 0)
        return true;
 
    // If sum of each part is even but
    // there is atleast one 1
    if (c1 > 0)
        return true;
    else
        return false;
}
 
// Driver Code
public static void Main()
{
    int n = 3;
    int[] a = { 1, 1, 2 };
 
    if (isSpiltPossible(n, a))
        Console.WriteLine("YES");
    else
        Console.WriteLine("NO");
}
}
 
// This code is contributed by
// Code Mech

PHP

<?php
// PHP implementation of the above
// approach:
 
// Function to check if it is possible
// to split the array in two parts with
// equal sum
function isSpiltPossible($n, $a)
{
    $sum = 0; $c1 = 0;
 
    // Calculate sum of elements
    // and count of 1"s
    for ($i = 0; $i < $n; $i++)
    {
        $sum += $a[$i];
 
        if ($a[$i] == 1)
        {
            $c1++;
        }
    }
 
    // If total sum is odd, return False
    if($sum % 2 != 0)
        return false;
 
    // If sum of each part is even,
    // return True
    if (($sum / 2) % 2 == 0)
        return true;
 
    // If sum of each part is even but
    // there is atleast one 1
    if ($c1 > 0)
        return true;
    else
        return false;
}
 
// Driver Code
$n = 3;
$a = array( 1, 1, 2 );
 
if (isSpiltPossible($n, $a))
    echo("YES");
else
    echo("NO");
 
// This code is contributed by
// Code Mech
?>

Javascript

<script>
 
// Javascript implementation of the above approach
 
// Function to check if it is possible
// to split the array in two parts with
// equal sum
function isSpiltPossible(n, a)
{
    let sum = 0, c1 = 0;
 
    // Calculate sum of elements
    // and count of 1"s
    for (let i = 0; i < n; i++)
    {
        sum += a[i];
 
        if (a[i] == 1)
        {
            c1++;
        }
    }
 
    // If total sum is odd, return False
    if(sum % 2 != 0)
        return false;
 
    // If sum of each part is even,
    // return True
    if ((sum / 2) % 2 == 0)
        return true;
 
    // If sum of each part is even but
    // there is atleast one 1
    if (c1 > 0)
        return true;
    else
        return false;
}
 
// driver program
     
        let n = 3;
    let a = [ 1, 1, 2 ];
 
    if (isSpiltPossible(n, a))
        document.write("YES");
    else
        document.write("NO");
   
</script>

Output:

YES

Алгоритмы

Проверьте, можно ли разделить массив из 1 и 2 на 2 части с равной суммой

C++

Java

Python3

C#

PHP

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ