Рубрики

Найти наибольшее кратное 3 | Установите 1 (используя очередь)

Дан массив неотрицательных целых чисел. Найдите наибольшее кратное 3, которое можно сформировать из элементов массива.

Например, если входной массив равен {8, 1, 9}, выходной сигнал должен быть «9 8 1», а если входной массив равен {8, 1, 7, 6, 0}, выходной сигнал должен быть «8 7». 6 0 ”.

Метод 1 (грубая сила)
Простой и прямой подход заключается в создании всех комбинаций элементов и отслеживании наибольшего числа, которое делится на 3.

Сложность времени: O (nx 2 ^ n). Будет 2 ^ n комбинаций элементов массива. Для сравнения каждой комбинации с наибольшим числом пока может потребоваться O (n) времени.
Вспомогательный пробел: O (n) // во избежание переполнения целого числа предполагается, что наибольшее число хранится в виде массива.

Метод 2 (хитрый)
Эта проблема может быть эффективно решена с помощью O (n) дополнительного пространства. Этот метод основан на следующих фактах о числах, кратных 3.

1) Число кратно 3, если и только если сумма цифр числа кратна 3. Например, давайте рассмотрим 8760, это кратно 3, потому что сумма цифр равна 8 + 7+ 6+ 0 = 21, который кратен 3.

2) Если число кратно 3, то все его перестановки также кратны 3. Например, так как 6078 кратно 3, числа 8760, 7608, 7068,… .. также кратны 3.

3) Мы получаем тот же остаток, когда делим число и сумму цифр числа. Например, если разделить число 151 и сумму его цифр 7 на 3, мы получим такой же остаток 1.

Какова идея вышеупомянутых фактов?
Значение 10% 3 и 100% 3 равно 1. То же самое верно для всех высших степеней 10, потому что 3 делит 9, 99, 999 и т. Д.
Давайте рассмотрим трехзначное число n, чтобы доказать вышеуказанные факты. Пусть первая, вторая и третья цифры n будут «a», «b» и «c» соответственно. п можно записать как

n = 100.a + 10.b + c 

Поскольку (10 ^ x)% 3 равно 1 для любого x, вышеприведенное выражение дает тот же остаток, что и следующее выражение

 1.a + 1.b + c 

Таким образом, остаток, полученный суммой цифр и 'n', одинаков.

Ниже приведено решение, основанное на приведенном выше наблюдении.

1. Сортировать массив в порядке убывания.

2. Возьмите три очереди. Один для хранения элементов, который при делении на 3 дает остаток как 0. Вторая очередь хранит цифры, которые при делении на 3 дают остаток как 1. Третья очередь хранит цифры, которые при делении на 3 дают остаток как 2. Вызовите их как очередь0, очередь1 и очередь2

3. Найдите сумму всех цифр.

4. Возникают три случая:
…… 4.1 . Сумма цифр делится на 3. Удалить все цифры из трех очередей. Сортируйте их по возрастанию. Выведите массив.

…… 4.2 Сумма цифр дает остаток 1 при делении на 3.
Удалить один элемент из очереди1. Если очередь1 пуста, удалите два элемента из очереди2. Если очередь2 содержит менее двух элементов, это число невозможно.

…… 4.3 Сумма цифр дает остаток 2 при делении на 3.
Удалить один элемент из очереди2. Если очередь2 пуста, удалите два элемента из очереди1. Если очередь1 содержит менее двух элементов, это число невозможно.

5. Наконец, опустошите все очереди во вспомогательный массив. Сортировать вспомогательный массив в порядке возрастания. Выведите вспомогательный массив.

Приведенный ниже код работает, только если входные массивы имеют числа от 0 до 9. Он может быть легко расширен для любого массива натуральных чисел. Нам просто нужно изменить часть, где мы сортируем массив в порядке убывания, в конце кода.

C ++

// C ++ реализация вышеуказанного подхода
#include <bits/stdc++.h>

using namespace std;

  
// Эта функция помещает все элементы 3 очередей во вспомогательный массив

void populateAux(int aux[], queue<int> queue0, queue<int> queue1,

                 queue<int> queue2, int* top)

{

    // Поместить все элементы первой очереди в aux []

    while (!queue0.empty()) {

        aux[(*top)++] = queue0.front();

        queue0.pop();

    }

  

    // Поместить все элементы второй очереди в aux []

    while (!queue1.empty()) {

        aux[(*top)++] = queue1.front();

        queue1.pop();

    }

  

    // Поместить все элементы третьей очереди в aux []

    while (!queue2.empty()) {

        aux[(*top)++] = queue2.front();

        queue2.pop();

    }

}

  
// Основная функция, которая находит максимально возможное кратное
// 3, которая может быть сформирована элементами arr []

int findMaxMultupleOf3(int arr[], int size)

{

    // Шаг 1: сортировка массива в неубывающем порядке

    sort(arr, arr + size);

  

    // Создаем 3 очереди для хранения номеров с остатком 0, 1

    // и 2 соответственно

    queue<int> queue0, queue1, queue2;

  

    // Шаг 2 и 3 получаем сумму чисел и помещаем их в

    // соответствующие очереди

    int i, sum;

    for (i = 0, sum = 0; i < size; ++i) {

        sum += arr[i];

        if ((arr[i] % 3) == 0)

            queue0.push(arr[i]);

        else if ((arr[i] % 3) == 1)

            queue1.push(arr[i]);

        else

            queue2.push(arr[i]);

    }

  

    // Шаг 4.2: сумма производит остаток 1

    if ((sum % 3) == 1) {

        // либо удалить один элемент из очереди1

        if (!queue1.empty())

            queue1.pop();

  

        // или удалим два элемента из queue2

        else {

            if (!queue2.empty())

                queue2.pop();

            else

                return 0;

  

            if (!queue2.empty())

                queue2.pop();

            else

                return 0;

        }

    }

  

    // Шаг 4.3: сумма производит остаток 2

    else if ((sum % 3) == 2) {

        // либо удалить один элемент из очереди2

        if (!queue2.empty())

            queue2.pop();

  

        // или удалить два элемента из очереди1

        else {

            if (!queue1.empty())

                queue1.pop();

            else

                return 0;

  

            if (!queue1.empty())

                queue1.pop();

            else

                return 0;

        }

    }

  

    int aux[size], top = 0;

  

    // Очистить все очереди во вспомогательный массив.

    populateAux(aux, queue0, queue1, queue2, &top);

  

    // сортируем массив по возрастанию

    sort(aux, aux + top, greater<int>());

  

    // распечатать результат

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

        cout << aux[i] << " ";

  

    return top;

}

int main()

{

  

    int arr[] = { 8, 1, 7, 6, 0 };

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

  

    if (findMaxMultupleOf3(arr, size) == 0)

        cout << "Not Possible";

  

    return 0;

}

С

/ * Программа для поиска наибольшего кратного 3 из массива элементов * /
#include <stdio.h>
#include <stdlib.h>

  
// Узел очереди

typedef struct Queue {

    int front;

    int rear;

    int capacity;

    int* array;

} Queue;

  
// Служебная функция для создания очереди с заданной емкостью

Queue* createQueue(int capacity)

{

    Queue* queue = (Queue*)malloc(sizeof(Queue));

    queue->capacity = capacity;

    queue->front = queue->rear = -1;

    queue->array = (int*)malloc(queue->capacity * sizeof(int));

    return queue;

}

  
// Утилита для проверки, пуста ли очередь

int isEmpty(Queue* queue)

{

    return queue->front == -1;

}

  
// Функция для добавления элемента в очередь

void Enqueue(Queue* queue, int item)

{

    queue->array[++queue->rear] = item;

    if (isEmpty(queue))

        ++queue->front;

}

  
// Функция для удаления элемента из очереди

int Dequeue(Queue* queue)

{

    int item = queue->array[queue->front];

    if (queue->front == queue->rear)

        queue->front = queue->rear = -1;

    else

        queue->front++;

  

    return item;

}

  
// Утилита для печати содержимого массива

void printArr(int* arr, int size)

{

    int i;

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

        printf("%d ", arr[i]);

}

  
/ * Следующие две функции необходимы для библиотечной функции qsort ().

   Обратитесь по следующей ссылке за помощью qsort ()

   http: // www.cplusplus.com/reference/clibrary/cstdlib/qsort/ * /

int compareAsc(const void* a, const void* b)

{

    return *(int*)a > *(int*)b;

}

int compareDesc(const void* a, const void* b)

{

    return *(int*)a < *(int*)b;

}

  
// Эта функция помещает все элементы 3 очередей во вспомогательный массив

void populateAux(int* aux, Queue* queue0, Queue* queue1,

                 Queue* queue2, int* top)

{

    // Поместить все элементы первой очереди в aux []

    while (!isEmpty(queue0))

        aux[(*top)++] = Dequeue(queue0);

  

    // Поместить все элементы второй очереди в aux []

    while (!isEmpty(queue1))

        aux[(*top)++] = Dequeue(queue1);

  

    // Поместить все элементы третьей очереди в aux []

    while (!isEmpty(queue2))

        aux[(*top)++] = Dequeue(queue2);

}

  
// Основная функция, которая находит максимально возможное кратное
// 3, которая может быть сформирована элементами arr []

int findMaxMultupleOf3(int* arr, int size)

{

    // Шаг 1: сортировка массива в неубывающем порядке

    qsort(arr, size, sizeof(int), compareAsc);

  

    // Создаем 3 очереди для хранения номеров с остатком 0, 1

    // и 2 соответственно

    Queue* queue0 = createQueue(size);

    Queue* queue1 = createQueue(size);

    Queue* queue2 = createQueue(size);

  

    // Шаг 2 и 3 получаем сумму чисел и помещаем их в

    // соответствующие очереди

    int i, sum;

    for (i = 0, sum = 0; i < size; ++i) {

        sum += arr[i];

        if ((arr[i] % 3) == 0)

            Enqueue(queue0, arr[i]);

        else if ((arr[i] % 3) == 1)

            Enqueue(queue1, arr[i]);

        else

            Enqueue(queue2, arr[i]);

    }

  

    // Шаг 4.2: сумма производит остаток 1

    if ((sum % 3) == 1) {

        // либо удалить один элемент из очереди1

        if (!isEmpty(queue1))

            Dequeue(queue1);

  

        // или удалим два элемента из queue2

        else {

            if (!isEmpty(queue2))

                Dequeue(queue2);

            else

                return 0;

  

            if (!isEmpty(queue2))

                Dequeue(queue2);

            else

                return 0;

        }

    }

  

    // Шаг 4.3: сумма производит остаток 2

    else if ((sum % 3) == 2) {

        // либо удалить один элемент из очереди2

        if (!isEmpty(queue2))

            Dequeue(queue2);

  

        // или удалить два элемента из очереди1

        else {

            if (!isEmpty(queue1))

                Dequeue(queue1);

            else

                return 0;

  

            if (!isEmpty(queue1))

                Dequeue(queue1);

            else

                return 0;

        }

    }

  

    int aux[size], top = 0;

  

    // Очистить все очереди во вспомогательный массив.

    populateAux(aux, queue0, queue1, queue2, &top);

  

    // сортируем массив по возрастанию

    qsort(aux, top, sizeof(int), compareDesc);

  

    // распечатать результат

    printArr(aux, top);

  

    return top;

}

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

int main()

{

    int arr[] = { 8, 1, 7, 6, 0 };

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

  

    if (findMaxMultupleOf3(arr, size) == 0)

        printf("Not Possible");

  

    return 0;

}

Джава

/ * Java-программа для поиска наибольшего числа
из 3, которые могут быть сформированы из массива
элементов * /

import java.util.Arrays;

import java.util.Queue;

import java.util.LinkedList;

import java.util.Collections;

  

public class Geeks {

  

    // Эта функция помещает все элементы 3 очередей в

    // вспомогательный массив

    public static int populateAux(int aux[], Queue<Integer> queue0, 

                        Queue<Integer> queue1, Queue<Integer> queue2)

    {

        int top=0;

        // Поместить все элементы первой очереди в aux []

        while(!queue0.isEmpty())

        {

            aux[top++]=queue0.remove();

        }

  

        // Поместить все элементы второй очереди в aux []

        while(!queue1.isEmpty())

        {

            aux[top++]=queue1.remove();

        }

  

        // Поместить все элементы третьей очереди в aux []

        while(!queue2.isEmpty())

        {

            aux[top++]=queue2.remove();

        }

  

        // Возвращаем число, добавленное к aux []

        return top;

    }

  

    // Основная функция, которая находит максимально возможное кратное

    // 3, которая может быть сформирована элементами arr []

    public static boolean findMaxMultupleOf3(int arr[])

    {

        // Шаг 1: сортировка массива в неубывающем порядке

        Arrays.sort(arr);

  

        // Создаем 3 очереди для хранения номеров с остатком 0, 1

        // и 2 соответственно

        Queue<Integer> queue0=new LinkedList<>();

        Queue<Integer> queue1=new LinkedList<>();

        Queue<Integer> queue2=new LinkedList<>();

  

        // Шаг 2 и 3 получаем сумму чисел и помещаем их в

        // соответствующие очереди

        int sum=0;

        for (int i = 0; i < arr.length; ++i) 

        

            sum += arr[i]; 

            if ((arr[i] % 3) == 0

                queue0.add(arr[i]); 

            else if ((arr[i] % 3) == 1

                queue1.add(arr[i]); 

            else

                queue2.add(arr[i]); 

        }

  

        // Шаг 4.2: сумма производит остаток 1

        if ((sum % 3) == 1

        

            // либо удалить один элемент из очереди1

            if (!queue1.isEmpty()) 

                queue1.remove(); 

  

            // или удалим два элемента из queue2

            else

            

                if (!queue2.isEmpty()) 

                    queue2.remove(); 

                else

                    return false

  

                if (!queue2.isEmpty()) 

                    queue2.remove(); 

                else

                    return false

            

        }

        // Шаг 4.3: сумма производит остаток 2

        else if ((sum % 3) == 2

        

            // либо удалить один элемент из очереди2

            if (!queue2.isEmpty()) 

                queue2.remove(); 

            // или удалить два элемента из очереди1

            else

            

                if (!queue1.isEmpty()) 

                    queue1.remove(); 

                else

                    return false

  

                if (!queue1.isEmpty()) 

                    queue1.remove(); 

                else

                    return false

            

        }

          

        int aux[]=new int[arr.length];

        // Очистить все очереди во вспомогательный массив

        // и получаем количество целых чисел, добавленных в aux []

        int top=populateAux(aux,queue0,queue1,queue2);

  

        // сортируем массив по возрастанию

        Arrays.sort(aux,0,top);

  

        // распечатать результат

        for (int i = top-1; i>=0; i--) 

            System.out.print(aux[i]+" ") ;

  

        return true;

    }

  

    public static void main(String args[])

    {

        int arr[] = { 8, 1, 7, 6, 0 };

        if (!findMaxMultupleOf3(arr)) 

        System.out.println("Not possible") ;

    }

}

  
// Этот код предоставлен Гауравом Тивари

C #

/ * C # программа для поиска наибольшего кратного
из 3, которые могут быть сформированы из массива
элементов * /

using System;

using System.Collections.Generic;

  

class Geeks 

{

  

    // Эта функция помещает все элементы 3 очередей в

    // вспомогательный массив

    public static int populateAux(int []aux, Queue<int> queue0, 

                        Queue<int> queue1, Queue<int> queue2)

    {

        int top = 0;

        // Поместить все элементы первой очереди в aux []

        while(queue0.Count != 0)

        {

            aux[top++] = queue0.Dequeue();

        }

  

        // Поместить все элементы второй очереди в aux []

        while(queue1.Count != 0)

        {

            aux[top++] = queue1.Dequeue();

        }

  

        // Поместить все элементы третьей очереди в aux []

        while(queue2.Count != 0)

        {

            aux[top++] = queue2.Dequeue();

        }

  

        // Возвращаем число, добавленное к aux []

        return top;

    }

  

    // Основная функция, которая находит максимально возможное кратное

    // 3, которая может быть сформирована элементами arr []

    public static bool findMaxMultupleOf3(int []arr)

    {

        // Шаг 1: сортировка массива в неубывающем порядке

        Array.Sort(arr);

  

        // Создаем 3 очереди для хранения номеров с остатком 0, 1

        // и 2 соответственно

        Queue<int> queue0 = new Queue<int>();

        Queue<int> queue1 = new Queue<int>();

        Queue<int> queue2 = new Queue<int>();

  

        // Шаг 2 и 3 получаем сумму чисел и помещаем их в

        // соответствующие очереди

        int sum=0;

        for (int i = 0; i < arr.Length; ++i) 

        

            sum += arr[i]; 

            if ((arr[i] % 3) == 0) 

                queue0.Enqueue(arr[i]); 

            else if ((arr[i] % 3) == 1) 

                queue1.Enqueue(arr[i]); 

            else

                queue2.Enqueue(arr[i]); 

        }

  

        // Шаг 4.2: сумма производит остаток 1

        if ((sum % 3) == 1) 

        

            // либо удалить один элемент из очереди1

            if (queue1.Count != 0) 

                queue1.Dequeue(); 

  

            // или удалим два элемента из queue2

            else

            

                if (queue2.Count != 0) 

                    queue2.Dequeue(); 

                else

                    return false

  

                if (queue2.Count != 0) 

                    queue2.Dequeue(); 

                else

                    return false

            

        }

        // Шаг 4.3: сумма производит остаток 2

        else if ((sum % 3) == 2) 

        

            // либо удалить один элемент из очереди2

            if (queue2.Count != 0) 

                queue2.Dequeue(); 

            // или удалить два элемента из очереди1

            else

            

                if (queue1.Count != 0) 

                    queue1.Dequeue(); 

                else

                    return false

  

                if (queue1.Count != 0) 

                    queue1.Dequeue(); 

                else

                    return false

            

        }

          

        int []aux = new int[arr.Length];

          

        // Очистить все очереди во вспомогательный массив

        // и получаем количество целых чисел, добавленных в aux []

        int top = populateAux(aux,queue0,queue1,queue2);

  

        // сортируем массив по возрастанию

        Array.Sort(aux,0,top);

  

        // распечатать результат

        for (int i = top-1; i >= 0; i--) 

            Console.Write(aux[i]+" ") ;

  

        return true;

    }

  

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

    public static void Main()

    {

        int []arr = { 8, 1, 7, 6, 0 };

        if (!findMaxMultupleOf3(arr)) 

        Console.WriteLine("Not possible") ;

    }

}

  
/ * Этот код предоставлен PrinciRaj1992 * /

Выход:

8 7 6 0

Вышеуказанный способ может быть оптимизирован следующими способами.
1) Мы можем использовать сортировку кучи или сортировку слиянием, чтобы сделать временную сложность O (nLogn).

2) Мы можем избежать лишнего места для очередей. Мы знаем, что максимум два элемента будут удалены из входного массива. Таким образом, мы можем отслеживать два элемента в двух переменных.

3) В конце, вместо сортировки массива снова в порядке убывания, мы можем напечатать отсортированный по возрастанию массив в обратном порядке. При печати в обратном порядке, мы можем пропустить два элемента, которые будут удалены.

Сложность времени: O (nLogn), предполагая, что алгоритм O (nLogn) используется для сортировки.

Найти наибольшее кратное 3 | Установите 2 (В O (n) время и O (1) пространство)

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

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

Найти наибольшее кратное 3 | Установите 1 (используя очередь)

0.00 (0%) 0 votes