Количество групп размеров два или три делится на 3

30.12.2019Математика

Вам дано N разных номеров. Перед вами стоит задача найти количество групп из 2 или 3, которые можно сформировать, сумма которых делится на три.

Примеры :

Input  : 1 5 7 2 9 14
Output : 13
The groups of two that can be 
formed are:
(1, 5)
(5, 7)
(1, 2)
(2, 7)
(1, 14)
(7, 14)
The groups of three are:
(1, 5, 9)
(5, 7, 9)
(1, 2, 9)
(2, 7, 9)
(2, 5, 14)
(1, 9, 14)
(7, 9, 14)

Input  : 3 6 9 12
Output : 10
All groups of 2 and 3 are valid.

Наивный подход: для каждого числа мы можем сложить его с любым другим числом и посмотреть, делится ли сумма на 3. Затем мы сохраняем эти суммы, чтобы мы могли снова добавить каждое число, чтобы проверить группы по три.
Сложность времени: O (N ^ 2) для групп из 2, O (N ^ 3) для групп из 3
Вспомогательное пространство: O (N ^ 2)

Оптимальный подход
Если мы внимательно посмотрим на каждое число, мы поймем, что существует 3 варианта:

Число делится на 3
Число оставляет остаток от 1, когда делится на 3
Число оставляет остаток от 2, когда делится на 3

Теперь, когда группы из двух делятся на 3, либо оба числа должны принадлежать категории 1 (оба делятся на 3), либо одно число должно оставить остаток 1, а другой остаток 2. Таким образом, остатки складываются до 3, делая сумму, делимую на 3.
Чтобы сформировать группу из трех, либо все три числа должны давать одинаковый остаток, либо одно должно давать остаток 0, другое должно давать 1, а последнее должно давать 2.

Таким образом, мы заботимся не о самих числах, а об их соответствующих остатках. Таким образом, сгруппировав их по трем категориям, мы можем найти все возможные группы, используя простую формулу.
Пусть C1 число элементов, делимых на 3.
Пусть C2 будет количеством элементов, оставшихся от остатка 1.
Пусть C3 будет количеством элементов, оставшихся от остатка 2.

Answer = 
C2 * C3 + C1 * (C1 - 1) / 2    --> Groups of 2
+ C1 * (C1 - 1) * (C1 - 2) / 6 
+ C2 * (C2 - 1) * (C2 - 2) / 6 
+ C3 * (C3 - 1) * (C3 - 2) / 6 --> Groups of 3 
                   with elements of same remainder
+ C1 * C2 * C3 --> Groups of three with all
                         distinct remainders

CPP

// Программа для поиска групп из 2 или 3
// чья сумма делится на 3
#include <iostream>

using namespace std;

int numOfCombinations(int arr[], int N)

{

// Инициализируем группы в 0

int C[3] = { 0, 0, 0 };

// Приращение группы с указанным остатком

for (int i = 0; i < N; ++i)

++C[arr[i] % 3];

// Возвращаем группы по формуле

return C[1] * C[2] + C[0] * (C[0] - 1) / 2 + C[0] * (C[0] - 1) * (C[0] - 2) / 6 + C[1] * (C[1] - 1) * (C[1] - 2) / 6 + C[2] * (C[2] - 1) * (C[2] - 2) / 6 + C[0] * C[1] * C[2];

}

// Функция драйвера

int main()

{

int arr1[6] = { 1, 5, 7, 2, 9, 14 };

cout << numOfCombinations(arr1, 6) << "\n";

int arr2[4] = { 3, 6, 9, 12 };

cout << numOfCombinations(arr2, 4) << "\n";

return 0;

}

Джава

// Программа для поиска групп из 2 или 3
// чья сумма делится на 3

class GFG {

static int numOfCombinations(int arr[], int N)

{

// Инициализируем группы в 0

int C[] = { 0, 0, 0 };

// Приращение группы с указанным остатком

for (int i = 0; i < N; ++i)

++C[arr[i] % 3];

// Возвращаем группы по формуле

return C[1] * C[2] + C[0] * (C[0] - 1) / 2 + C[0] * (C[0] - 1) * (C[0] - 2) / 6 + C[1] * (C[1] - 1) * (C[1] - 2) / 6 + C[2] * (C[2] - 1) * (C[2] - 2) / 6 + C[0] * C[1] * C[2];

}

// Код драйвера

public static void main(String[] args)

{

int arr1[] = { 1, 5, 7, 2, 9, 14 };

System.out.print(numOfCombinations(arr1, 6) + "\n");

int arr2[] = { 3, 6, 9, 12 };

System.out.print(numOfCombinations(arr2, 4) + "\n");

}

// Этот код предоставлен Anant Agarwal.

python3

# Программа для поиска групп из 2 или 3
# чья сумма делится на 3

def numOfCombinations(arr, N):

# Инициализировать группы до 0

C = [0, 0, 0]

# Группа приращений с

# указанный остаток

for i in range(N):

C[arr[i] % 3]= C[arr[i] % 3]+1

# Вернуть группы по формуле

return (C[1] * C[2] + C[0] * (C[0] - 1) / 2 + C[0] * (C[0] - 1) * (C[0] - 2) / 6 + C[1] * (C[1] - 1) * (C[1] - 2) / 6 + C[2] * (C[2] - 1) * (C[2] - 2) / 6 + C[0] * C[1] * C[2])

# Код драйвера

arr1 = [1, 5, 7, 2, 9, 14]

print(int(numOfCombinations(arr1, 6)))

arr2 = [3, 6, 9, 12]

print(int(numOfCombinations(arr2, 4)))

# Этот код добавлен
# Анант Агарвал.

C #

// C # Программа для поиска групп из 2 или
// 3, чья сумма делится на 3

using System;

class GFG {

// Функция для поиска количества комбинаций

static int numOfCombinations(int[] arr,

int N)

{

// Инициализируем группы в 0

int[] C = { 0, 0, 0 };

// Приращение группы с указанным остатком

for (int i = 0; i < N; ++i)

++C[arr[i] % 3];

// Возвращаем группы по формуле

return C[1] * C[2] + C[0] * (C[0] - 1) / 2 + C[0] * (C[0] - 1) * (C[0] - 2) / 6 + C[1] * (C[1] - 1) * (C[1] - 2) / 6 + C[2] * (C[2] - 1) * (C[2] - 2) / 6 + C[0] * C[1] * C[2];

}

// Код драйвера

public static void Main()

{

int[] arr1 = { 1, 5, 7, 2, 9, 14 };

Console.WriteLine(numOfCombinations(arr1, 6));

int[] arr2 = { 3, 6, 9, 12 };

Console.WriteLine(numOfCombinations(arr2, 4));

}

// Этот код предоставлен vt_m.

PHP

<?php

// PHP программа для поиска
// группы по 2 или 3
// чья сумма делится на 3

function numOfCombinations($arr, $N)

{

// Инициализируем группы в 0

$C = array(0, 0, 0);

// Увеличиваем группу с

// указанный остаток

for ($i = 0; $i < $N; ++$i)

++$C[$arr[$i] % 3];

// Возвращаем группы по формуле

return $C[1] * $C[2] +

$C[0] * ($C[0] - 1) / 2 +

$C[0] * ($C[0] - 1) *

($C[0] - 2) / 6 +

$C[1] * ($C[1] - 1) *

($C[1] - 2) / 6 +

$C[2] * ($C[2] - 1) *

($C[2] - 2) / 6 +

$C[0] * $C[1] * $C[2];

}

// Код драйвера

$arr1 = array(1, 5, 7, 2, 9, 14);

echo numOfCombinations($arr1, 6), "\n";

$arr2 = array(3, 6, 9, 12);

echo numOfCombinations($arr2, 4), "\n";

// Этот код предоставлен ajit
?>

Выход :

13
10

Спросил в Амазонке

Эта статья предоставлена Адитьей Каматом . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Количество групп размеров два или три делится на 3

0.00 (0%) 0 votes