Рубрики

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

Учитывая несортированный массив целых (только положительные значения) размера 'n', мы можем сформировать группу из двух или трех, группа должна быть такой, чтобы сумма всех элементов в этой группе была кратна 3. Подсчитать все возможное количество групп, которые могут быть сгенерированы таким образом.
Примеры:

Input: arr[] = {3, 6, 7, 2, 9}
Output: 8
// Groups are {3,6}, {3,9}, {9,6}, {7,2}, {3,6,9},
//            {3,7,2}, {7,2,6}, {7,2,9}


Input: arr[] = {2, 1, 3, 4}
Output: 4
// Groups are {2,1}, {2,4}, {2,1,3}, {2,4,3}

Идея состоит в том, чтобы увидеть остаток каждого элемента при делении на 3. Набор элементов может образовывать группу, только если их количество остатков кратно 3.
Например: 8, 4, 12. Теперь остатки равны 2, 1 и 0 соответственно. Это означает, что 8 на расстоянии 2 от 3-кратного (6), 4 на расстоянии 1 от 3-кратного (3) и 12 на 0. Таким образом, мы можем записать сумму как 8 (можно записать как 6 + 2), 4 (можно записать как 3 + 1) и 12 (можно записать как 12 + 0). Теперь сумма 8, 4 и 12 может быть записана как 6 + 2 + 3 + 1 + 12 + 0. Теперь 6 + 3 + 12 всегда будет делиться на 3, так как все члены кратны трем. Теперь нам нужно только проверить, делится ли 2 + 1 + 0 (остатки) на 3 или нет, что делает полную сумму делимой на 3.
Поскольку задача состоит в перечислении групп, мы считаем все элементы с разными остатками.

1. Hash all elements in a count array based on remainder, i.e, 
   for all elements a[i], do c[a[i]%3]++;
2. Now c[0] contains the number of elements which when divided
   by 3 leave remainder 0 and similarly c[1] for remainder 1 
   and c[2] for 2.
3. Now for group of 2, we have 2 possibilities
   a. 2 elements of remainder 0 group. Such possibilities are 
      c[0]*(c[0]-1)/2
   b. 1 element of remainder 1 and 1 from remainder 2 group
      Such groups are c[1]*c[2].
4. Now for group of 3,we have 4 possibilities
   a. 3 elements from remainder group 0.
      No. of such groups are c[0]C3
   b. 3 elements from remainder group 1.
      No. of such groups are c[1]C3
   c. 3 elements from remainder group 2.
      No. of such groups are c[2]C3
   d. 1 element from each of 3 groups. 
      No. of such groups are c[0]*c[1]*c[2].
5. Add all the groups in steps 3 and 4 to obtain the result.

C ++

// C ++ Программа для подсчета всего возможного
// группы размером 2 или 3, которые имеют
// сумма, кратная 3

  
#include<bits/stdc++.h>

using namespace std;

  
// Возвращает количество всех возможных групп
// который может быть сформирован из элементов a [].

int findgroups(int arr[], int n)

{

    // Создать массив C [3] для хранения счетчиков

    // элементов с остатками 0, 1 и 2.

    // c [i] будет хранить количество элементов

    // с остатком i

    int c[3] = {0}, i;

  

    int res = 0; // Для сохранения результата

  

    // Считаем элементы с остатками 0, 1 и 2

    for (i=0; i<n; i++)

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

  

    // Случай 3.a: Подсчет групп размера 2

    // из 0 оставшихся элементов

    res += ((c[0]*(c[0]-1))>>1);

  

    // Случай 3.b: Подсчет групп размера 2 с

    // один элемент с 1 остатком и другой

    // с 2 остатками

    res += c[1] * c[2];

  

    // Случай 4.a: Подсчет групп размера 3

    // со всеми 0 остальными элементами

    res += (c[0] * (c[0]-1) * (c[0]-2))/6;

  

    // Случай 4.b: Подсчет групп размера 3

    // со всеми 1 остальными элементами

    res += (c[1] * (c[1]-1) * (c[1]-2))/6;

  

    // Случай 4.c: Количество групп размера 3

    // со всеми 2 остальными элементами

    res += ((c[2]*(c[2]-1)*(c[2]-2))/6);

  

    // Случай 4.c: Количество групп размера 3

    // с разными остатками

    res += c[0]*c[1]*c[2];

  

    // Возвращаем общее количество сохраненных в res

    return res;

}

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

int main()

{

    int arr[] = {3, 6, 7, 2, 9};

    int n = sizeof(arr)/sizeof(arr[0]);

    cout << "Required number of groups are " 

         << findgroups(arr,n) << endl;

    return 0;

}

  
// Этот код добавлен
// Аканкша Рай

С

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

  
#include<stdio.h>

  
// Возвращает количество всех возможных групп, которые могут быть сформированы из элементов
// из [].

int findgroups(int arr[], int n)

{

    // Создаем массив C [3] для хранения количества элементов с остатком

    // 0, 1 и 2. c [i] будет хранить количество элементов с остатком i

    int c[3] = {0}, i;

  

    int res = 0; // Для сохранения результата

  

    // Считаем элементы с остатками 0, 1 и 2

    for (i=0; i<n; i++)

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

  

    // Случай 3.a: Подсчет групп размера 2 из 0 оставшихся элементов

    res += ((c[0]*(c[0]-1))>>1);

  

    // Случай 3.b: Подсчет групп размера 2 с одним элементом с 1

    // остаток и другое с 2 остатками

    res += c[1] * c[2];

  

    // Случай 4.a: Подсчет групп размера 3 со всеми 0 остальными элементами

    res += (c[0] * (c[0]-1) * (c[0]-2))/6;

  

    // Случай 4.b: Подсчитать группы размера 3 со всеми 1 остальными элементами

    res += (c[1] * (c[1]-1) * (c[1]-2))/6;

  

    // Случай 4.c: Подсчет групп размера 3 со всеми 2 оставшимися элементами

    res += ((c[2]*(c[2]-1)*(c[2]-2))/6);

  

    // Случай 4.c: Подсчет групп размера 3 с разными остатками

    res += c[0]*c[1]*c[2];

  

    // Возвращаем общее количество сохраненных в res

    return res;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int arr[] = {3, 6, 7, 2, 9};

    int n = sizeof(arr)/sizeof(arr[0]);

    printf("Required number of groups are %d\n", findgroups(arr,n));

    return 0;

}

Джава

// Java-программа для подсчета всего возможного
// группы размером 2 или 3, которые имеют
// сумма, кратная 3

class FindGroups 

{

    // Возвращает количество всех возможных групп, которые могут быть сформированы из элементов

    // из [].

  

    int findgroups(int arr[], int n) 

    {

        // Создаем массив C [3] для хранения количества элементов с остатком

        // 0, 1 и 2. c [i] будет хранить количество элементов с остатком i

        int c[] = new int[]{0, 0, 0};

        int i;

  

        int res = 0; // Для сохранения результата

  

        // Считаем элементы с остатками 0, 1 и 2

        for (i = 0; i < n; i++)

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

  

        // Случай 3.a: Подсчет групп размера 2 из 0 оставшихся элементов

        res += ((c[0] * (c[0] - 1)) >> 1);

  

        // Случай 3.b: Подсчет групп размера 2 с одним элементом с 1

        // остаток и другое с 2 остатками

        res += c[1] * c[2];

  

        // Случай 4.a: Подсчет групп размера 3 со всеми 0 остальными элементами

        res += (c[0] * (c[0] - 1) * (c[0] - 2)) / 6;

  

        // Случай 4.b: Подсчитать группы размера 3 со всеми 1 остальными элементами

        res += (c[1] * (c[1] - 1) * (c[1] - 2)) / 6;

  

        // Случай 4.c: Подсчет групп размера 3 со всеми 2 оставшимися элементами

        res += ((c[2] * (c[2] - 1) * (c[2] - 2)) / 6);

  

        // Случай 4.c: Подсчет групп размера 3 с разными остатками

        res += c[0] * c[1] * c[2];

  

        // Возвращаем общее количество сохраненных в res

        return res;

    }

  

    public static void main(String[] args) 

    {

        FindGroups groups = new FindGroups();

        int arr[] = {3, 6, 7, 2, 9};

        int n = arr.length;

        System.out.println("Required number of groups are "

                + groups.findgroups(arr, n));

    }

}

python3

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

  
# Возвращает количество всех возможных
# группы, которые могут быть сформированы
# из элементов [].

def findgroups(arr, n):

  

    # Создать массив C [3] для хранения

    # количество элементов с

    # остатки 0, 1 и 2. c [i]

    # будет хранить количество элементов

    # с остатком я

    c = [0, 0, 0]

  

    # Чтобы сохранить результат

    res = 0 

  

    # Количество элементов с остатком

    № 0, 1 и 2

    for i in range(0, n):

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

  

    # Случай 3.a: Подсчет групп по размеру

    № 2 из 0 оставшихся элементов

    res += ((c[0] * (c[0] - 1)) >> 1)

  

    # Случай 3.b: Подсчет групп по размеру

    # 2 с одним элементом с 1

    # остаток и прочее с 2 остатками

    res += c[1] * c[2]

  

    # Случай 4.a: Подсчет групп по размеру

    # 3 со всеми 0 остальными элементами

    res += (c[0] * (c[0] - 1) * (c[0] - 2)) / 6

  

    # Случай 4.b: Подсчет групп размера 3

    # со всеми 1 остальными элементами

    res += (c[1] * (c[1] - 1) * (c[1] - 2)) / 6

  

    # Случай 4.c: Подсчет групп размера 3

    # со всеми 2 остальными элементами

    res += ((c[2] * (c[2] - 1) * (c[2] - 2)) / 6)

  

    # Случай 4.c: Подсчет групп размера 3

    # с разными остатками

    res += c[0] * c[1] * c[2]

  

    # Возвращаем общее количество сохраненных в res

    return res

  
# Драйверная программа

arr = [3, 6, 7, 2, 9]

n = len(arr)

  

print ("Required number of groups are",

               int(findgroups(arr, n)))

  
# Эта статья предоставлена shreyanshi_arun

C #

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

using System;

  

class FindGroups 

{

      

    // Возвращает количество всех возможных

    // группы, которые могут быть сформированы

    // из элементов a [].

  

    int findgroups(int []arr, int n) 

    {

          

        // Создать массив C [3] для хранения

        // количество элементов с остатком

        // 0, 1 и 2. c [i] будет хранить

        // количество элементов с остатком i

        int [] c= new int[]{0, 0, 0};

        int i;

  

        // Для сохранения результата

        int res = 0;

  

        // Считаем элементы с

        // остаток 0, 1 и 2

        for (i = 0; i < n; i++)

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

  

        // Случай 3.a: Подсчет групп по размеру

        // 2 из 0 остальных элементов

        res += ((c[0] * (c[0] - 1)) >> 1);

  

        // Случай 3.b: Подсчет групп размера 2

        // с одним элементом с 1 остатком

        // и другое с 2 остатками

        res += c[1] * c[2];

  

        // Случай 4.a: Подсчет групп размера 3

        // со всеми 0 остальными элементами

        res += (c[0] * (c[0] - 1) *

               (c[0] - 2)) / 6;

  

        // Случай 4.b: Подсчет групп размера 3

        // со всеми 1 остальными элементами

        res += (c[1] * (c[1] - 1) * 

               (c[1] - 2)) / 6;

  

        // Случай 4.c: Количество групп размера 3

        // со всеми 2 остальными элементами

        res += ((c[2] * (c[2] - 1) * 

                (c[2] - 2)) / 6);

  

        // Случай 4.c: Количество групп размера 3

        // с разными остатками

        res += c[0] * c[1] * c[2];

  

        // Возвращаем общее количество сохраненных в res

        return res;

    }

  

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

    public static void Main() 

    {

        FindGroups groups = new FindGroups();

        int []arr = {3, 6, 7, 2, 9};

        int n = arr.Length;

        Console.Write("Required number of groups are "

                       + groups.findgroups(arr, n));

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// Программа PHP для подсчета групп размера
// 2 или 3, сумма которых кратна 3

  
// Возвращает количество всех возможных групп
// который может быть сформирован из элементов a [].

function findgroups($arr, $n)

{

    // Создать массив C [3] для хранения счетчиков

    // элементов с остатками 0, 1 и 2.

    // c [i] будет хранить количество элементов

    // с остатком i

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

  

    // Для сохранения результата

    $res = 0;

  

    // Считаем элементы с остатком

    // 0, 1 и 2

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

        $c[$arr[$i] % 3] += 1;

  

    // Случай 3.a: Подсчет групп по размеру

    // 2 из 0 остальных элементов

    $res += (($c[0] * ($c[0] - 1)) >> 1);

  

    // Случай 3.b: Подсчет групп по размеру

    // 2 с одним элементом с 1

    // остаток и другое с 2 остатками

    $res += $c[1] * $c[2];

  

    // Случай 4.a: Подсчет групп по размеру

    // 3 со всеми 0 остальными элементами

    $res += ($c[0] * ($c[0] - 1) * 

            ($c[0] - 2)) / 6;

  

    // Случай 4.b: Подсчет групп размера 3

    // со всеми 1 остальными элементами

    $res += ($c[1] * ($c[1] - 1) * 

            ($c[1] - 2)) / 6;

  

    // Случай 4.c: Количество групп размера 3

    // со всеми 2 остальными элементами

    $res += (($c[2] * ($c[2] - 1) * 

             ($c[2] - 2)) / 6);

  

    // Случай 4.c: Количество групп размера 3

    // с разными остатками

    $res += $c[0] * $c[1] * $c[2];

  

    // Возвращаем общее количество сохраненных в res

    return $res;

}

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

$arr = array(3, 6, 7, 2, 9);

$n = count($arr);

  

echo "Required number of groups are "

           (int)(findgroups($arr, $n));

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


Выход:

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

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

0.00 (0%) 0 votes