Рубрики

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

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

Примеры:

Input : arr[] = {5, 4, 3, 1, 1} 
Output : 4311

Input : Arr[] = {5, 5, 5, 7} 
Output : 555 

Спросил в: Google Интервью

Мы обсудили решение на основе очередей . Оба решения (обсуждаемые в предыдущем и этом постах) основаны на том факте, что число делится на 3 тогда и только тогда, когда сумма цифр числа делится на 3.
Например, давайте рассмотрим 555, он делится на 3, потому что сумма цифр равна 5 + 5 + 5 = 15, что делится на 3. Если сумма цифр не делится на 3, то остаток должен быть либо 1, либо 2.
Если мы получим остаток «1» или «2», мы должны удалить максимум две цифры, чтобы сделать число, делимое на 3:

  1. Если остаток равен «1»: мы должны удалить одну цифру с остатком «1», или мы должны удалить две цифры с остатком «2» (2 + 2 => 4% 3 => «1»)
  2. Если остаток равен «2»:. Мы должны удалить одну цифру с остатком «2», или мы должны удалить две цифры с остатком «1» (1 + 1 => 2% 3 => 2).

Примеры :

Input : arr[] = 5, 5, 5, 7 
Sum of digits = 5 + 5 + 7 = 22
Remainder = 22 % 3 = 1 
We remove smallest single digit that 
has remainder '1'. We remove 7 % 3 = 1 
So largest number divisible by 3 is : 555

Let's take an another example :
Input : arr[]  = 4 , 4 , 1 , 1 , 1 , 3
Sum of digits  = 4 + 4 + 1 + 1 + 1 + 3 = 14
Reminder = 14 % 3 = 2 
We have to remove the smallest digit that 
has remainder ' 2 ' or two digits that have
remainder '1'. Here there is no digit with 
reminder '2', so we have to remove two smallest 
digits that have remainder '1'. The digits are : 
1, 1. So largest number divisible by 3 is 4 4 3 1 

Ниже приведена реализация вышеуказанной идеи.

C ++

// C ++ программа для поиска наибольшего числа
// это может быть режим из элементов
// массив и делится на 3
#include<bits/stdc++.h>

using namespace std;

  
// Количество цифр
#define MAX_SIZE 10

  
// функция сортировки массива цифр с помощью
// считает

void sortArrayUsingCounts(int arr[], int n)

{

    // Сохраняем количество всех элементов

    int count[MAX_SIZE] = {0};

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

        count[arr[i]]++;

  

    // Хранить

    int index = 0;

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

        while (count[i] > 0)

            arr[index++] = i, count[i]--;

}

  
// Удалить элементы из arr [] по индексам ind1 и ind2

bool removeAndPrintResult(int arr[], int n, int ind1,

                                        int ind2 = -1)

{

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

        if (i != ind1 && i != ind2)

            cout << arr[i] ;

}

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

bool largest3Multiple(int arr[], int n)

{

    // Сумма всего элемента массива

    int sum = accumulate(arr, arr+n, 0);

  

    // Сумма делится на 3, нет необходимости

    // удаляем элемент

    if (sum%3 == 0)

        return true ;

  

    // Сортировка элемента массива в порядке возрастания

    sortArrayUsingCounts(arr, n);

  

    // Найти напоминание

    int remainder = sum % 3;

  

    // Если остаток равен '1', мы должны удалить либо

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

    // от остатка '2'

    if (remainder == 1)

    {

        int rem_2[2];

        rem_2[0] = -1, rem_2[1] = -1;

  

        // Обход элементов массива

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

        {

            // Сохраняем первый элемент остатка '1'

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

            {

                removeAndPrintResult(arr, n, i);

                return true;

            }

  

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

            {

                // Если это первое вхождение остатка 2

                if (rem_2[0] == -1)

                    rem_2[0] = i;

  

                // Если второе вхождение

                else if (rem_2[1] == -1)

                    rem_2[1] = i;

            }

        }

  

        if (rem_2[0] != -1 && rem_2[1] != -1)

        {

            removeAndPrintResult(arr, n, rem_2[0], rem_2[1]);

            return true;

        }

    }

  

    // Если остаток равен 2, мы должны удалить либо

    // один элемент остатка '2' или два элемента

    // от остатка '1'

    else if (remainder == 2)

    {

        int rem_1[2];

        rem_1[0] = -1, rem_1[1] = -1;

  

        // пройти элементы массива

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

        {

            // сохраняем первый элемент остатка '2'

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

            {

                removeAndPrintResult(arr, n, i);

                return true;

            }

  

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

            {

                // Если это первое вхождение остатка 1

                if (rem_1[0] == -1)

                    rem_1[0] = i;

  

                // Если второе вхождение

                else if (rem_1[1] == -1)

                    rem_1[1] = i;

            }

        }

  

        if (rem_1[0] != -1 && rem_1[1] != -1)

        {

            removeAndPrintResult(arr, n, rem_1[0], rem_1[1]);

            return true;

        }

    }

  

    cout << "Not possible";

    return false;

}

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

int main()

{

    int arr[] = {4 , 4 , 1 , 1 , 1 , 3} ;

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

    largest3Multiple(arr, n);

    return 0;

}

Джава

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

import java.util.*;

  

class GFG 

{

  

    // Количество цифр

    static int MAX_SIZE = 10;

  

    // функция сортировки массива цифр с помощью

    // считает

    static void sortArrayUsingCounts(int arr[], 

                                     int n)

    {

        // Сохраняем количество всех элементов

        int[] count = new int[MAX_SIZE];

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

        {

            count[arr[i]]++;

        }

  

        // Хранить

        int index = 0;

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

        {

            while (count[i] > 0

            {

                arr[index++] = i;

                count[i]--;

            }

        }

    }

  

    // Удалить элементы из arr []

    // по индексам ind1 и ind2

    static void removeAndPrintResult(int arr[], int n, 

                                     int ind1, int ind2)

    {

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

        {

            if (i != ind1 && i != ind2) 

            {

                System.out.print(arr[i]);

            }

        }

    }

  

    // Возвращает наибольшее кратное 3

    // это можно сформировать используя

    // arr [] элементы.

    static boolean largest3Multiple(int arr[], 

                                    int n)

    {

        // Сумма всего элемента массива

        int sum = accumulate(arr, 0, n);

  

        // Если сумма делится на 3,

        // нет необходимости удалять элемент

        if (sum % 3 == 0

        {

            return true;

        }

  

        // Сортировка элемента массива в порядке возрастания

        sortArrayUsingCounts(arr, n);

  

        // Найти напоминание

        int remainder = sum % 3;

  

        // Если остаток равен '1', мы должны

        // удаляем один элемент

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

        // остаток '2'

        if (remainder == 1)

        {

            int[] rem_2 = new int[2];

            rem_2[0] = -1;

            rem_2[1] = -1;

  

            // Обход элементов массива

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

            {

                  

                // Сохраняем первый элемент остатка '1'

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

                {

                    removeAndPrintResult(arr, n, i, -1);

                    return true;

                }

  

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

                {

                      

                    // Если это первое вхождение

                    // от остатка 2

                    if (rem_2[0] == -1)

                    {

                        rem_2[0] = i;

                    }

                      

                    // Если второе вхождение

                    else if (rem_2[1] == -1

                    {

                        rem_2[1] = i;

                    }

                }

            }

  

            if (rem_2[0] != -1 && 

                rem_2[1] != -1

            {

                removeAndPrintResult(arr, n, rem_2[0], 

                                             rem_2[1]);

                return true;

            }

        

          

        // Если остаток равен '2', мы должны

        // удаляем один элемент

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

        // остаток '1'

        else if (remainder == 2

        {

            int[] rem_1 = new int[2];

            rem_1[0] = -1;

            rem_1[1] = -1;

  

            // пройти элементы массива

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

            {

                  

                // сохраняем первый элемент остатка '2'

                if (arr[i] % 3 == 2

                {

                    removeAndPrintResult(arr, n, i, -1);

                    return true;

                }

  

                if (arr[i] % 3 == 1

                {

                      

                    // Если это первое вхождение

                    // от остатка 1

                    if (rem_1[0] == -1

                    {

                        rem_1[0] = i;

                    

                      

                    // Если второе вхождение

                    else if (rem_1[1] == -1

                    {

                        rem_1[1] = i;

                    }

                }

            }

  

            if (rem_1[0] != -1 && 

                rem_1[1] != -1)

            {

                removeAndPrintResult(arr, n, rem_1[0], 

                                             rem_1[1]);

                return true;

            }

        }

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

        return false;

    }

  

    static int accumulate(int[] arr,

                          int start, 

                          int end) 

    {

        int sum = 0;

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

        {

            sum += arr[i];

        }

        return sum;

    }

      

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

    public static void main(String[] args)

    {

        int arr[] = {4, 4, 1, 1, 1, 3};

        int n = arr.length;

        largest3Multiple(arr, n);

    }

}

  
// Этот код добавлен
// Принси Сингх

python3

# Python программа для поиска наибольшего числа
# это может быть режим из элементов
# массив и делится на 3

  
Количество цифр

MAX_SIZE = 10

  
# функция для сортировки массива цифр с помощью
# рассчитывает

def sortArrayUsingCounts(arr, n):

  

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

    count = [0]*MAX_SIZE

    for i in range(n):

        count[arr[i]] += 1

  

    # Хранить

    index = 0

    for i in range(MAX_SIZE):

        while count[i] > 0:

            arr[index] = i

            index += 1

            count[i] -= 1

  

  
# Удалить элементы из arr [] по индексам ind1 и ind2

def removeAndPrintResult(arr, n, ind1, ind2=-1):

    for i in range(n-1, -1, -1):

        if i != ind1 and i != ind2:

            print(arr[i], end="")

  

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

def largest3Multiple(arr, n):

  

    # Сумма всего элемента массива

    s = sum(arr)

  

    # Сумма делится на 3, нет необходимости

    # удалить элемент

    if s % 3 == 0:

        return True

  

    # Сортировать элемент массива в порядке возрастания

    sortArrayUsingCounts(arr, n)

  

    # Найти напоминание

    remainder = s % 3

  

    # Если остаток равен «1», мы должны удалить либо

    # один элемент остатка '1' или два элемента

    № остатка '2'

    if remainder == 1:

        rem_2 = [0]*2

        rem_2[0] = -1; rem_2[1] = -1

  

        # Обход элементов массива

        for i in range(n):

  

            # Сохранить первый элемент остатка '1'

            if arr[i] % 3 == 1:

                removeAndPrintResult(arr, n, i)

                return True

  

            if arr[i] % 3 == 2:

  

                # Если это первое появление остатка 2

                if rem_2[0] == -1:

                    rem_2[0] = i

  

                # Если второе появление

                elif rem_2[1] == -1:

                    rem_2[1] = i

  

        if rem_2[0] != -1 and rem_2[1] != -1:

            removeAndPrintResult(arr, n, rem_2[0], rem_2[1])

            return True

  

    # Если остаток равен 2, мы должны удалить либо

    # один элемент остатка '2' или два элемента

    № остатка '1'

    elif remainder == 2:

        rem_1 = [0]*2

        rem_1[0] = -1; rem_1[1] = -1

  

        # элементы массива перемещения

        for i in range(n):

  

            # сохранить первый элемент остатка '2'

            if arr[i] % 3 == 2:

                removeAndPrintResult(arr, n, i)

                return True

  

            if arr[i] % 3 == 1:

  

                # Если это первое появление остатка 1

                if rem_1[0] == -1:

                    rem_1[0] = i

                  

                # Если второе появление

                elif rem_1[1] == -1:

                    rem_1[1] = i

                      

        if rem_1[0] != -1 and rem_1[1] != -1:

            removeAndPrintResult(arr, n, rem_1[0], rem_1[1])

            return True

  

    print("Not possible")

    return False

  

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

if __name__ == "__main__":

  

    arr = [4, 4, 1, 1, 1, 3]

    n = len(arr)

    largest3Multiple(arr, n)

  
# Этот код предоставлен
# sanjeev2552

C #

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

using System;

      

class GFG 

{

  

    // Количество цифр

    static int MAX_SIZE = 10;

  

    // функция сортировки массива цифр с помощью

    // считает

    static void sortArrayUsingCounts(int []arr, 

                                     int n)

    {

        // Сохраняем количество всех элементов

        int[] count = new int[MAX_SIZE];

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

        {

            count[arr[i]]++;

        }

  

        // Хранить

        int index = 0;

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

        {

            while (count[i] > 0) 

            {

                arr[index++] = i;

                count[i]--;

            }

        }

    }

  

    // Удалить элементы из arr []

    // по индексам ind1 и ind2

    static void removeAndPrintResult(int []arr, int n, 

                                     int ind1, int ind2)

    {

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

        {

            if (i != ind1 && i != ind2) 

            {

                Console.Write(arr[i]);

            }

        }

    }

  

    // Возвращает наибольшее кратное 3

    // это можно сформировать используя

    // arr [] элементы.

    static Boolean largest3Multiple(int []arr, 

                                    int n)

    {

        // Сумма всего элемента массива

        int sum = accumulate(arr, 0, n);

  

        // Если сумма делится на 3,

        // нет необходимости удалять элемент

        if (sum % 3 == 0) 

        {

            return true;

        }

  

        // Сортировка элемента массива в порядке возрастания

        sortArrayUsingCounts(arr, n);

  

        // Найти напоминание

        int remainder = sum % 3;

  

        // Если остаток равен '1', мы должны

        // удаляем один элемент

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

        // остаток '2'

        if (remainder == 1)

        {

            int[] rem_2 = new int[2];

            rem_2[0] = -1;

            rem_2[1] = -1;

  

            // Обход элементов массива

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

            {

                  

                // Сохраняем первый элемент остатка '1'

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

                {

                    removeAndPrintResult(arr, n, i, -1);

                    return true;

                }

  

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

                {

                      

                    // Если это первое вхождение

                    // от остатка 2

                    if (rem_2[0] == -1)

                    {

                        rem_2[0] = i;

                    }

                      

                    // Если второе вхождение

                    else if (rem_2[1] == -1) 

                    {

                        rem_2[1] = i;

                    }

                }

            }

  

            if (rem_2[0] != -1 && 

                rem_2[1] != -1) 

            {

                removeAndPrintResult(arr, n, rem_2[0], 

                                              rem_2[1]);

                return true;

            }

        

          

        // Если остаток равен '2', мы должны

        // удаляем один элемент

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

        // остаток '1'

        else if (remainder == 2) 

        {

            int[] rem_1 = new int[2];

            rem_1[0] = -1;

            rem_1[1] = -1;

  

            // пройти элементы массива

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

            {

                  

                // сохраняем первый элемент остатка '2'

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

                {

                    removeAndPrintResult(arr, n, i, -1);

                    return true;

                }

  

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

                {

                      

                    // Если это первое вхождение

                    // от остатка 1

                    if (rem_1[0] == -1) 

                    {

                        rem_1[0] = i;

                    

                      

                    // Если второе вхождение

                    else if (rem_1[1] == -1) 

                    {

                        rem_1[1] = i;

                    }

                }

            }

  

            if (rem_1[0] != -1 && 

                rem_1[1] != -1)

            {

                removeAndPrintResult(arr, n, rem_1[0], 

                                             rem_1[1]);

                return true;

            }

        }

        Console.Write("Not possible");

        return false;

    }

  

    static int accumulate(int[] arr,

                          int start, 

                          int end) 

    {

        int sum = 0;

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

        {

            sum += arr[i];

        }

        return sum;

    }

      

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

    public static void Main(String[] args)

    {

        int []arr = {4, 4, 1, 1, 1, 3};

        int n = arr.Length;

        largest3Multiple(arr, n);

    }

}

  
// Этот код предоставлен 29AjayKumar


Выход:

4431

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

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

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

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

0.00 (0%) 0 votes