Рубрики

Головоломка с массивом продуктов

Учитывая массив arr [] из n целых чисел, создайте Product Array prod [] (того же размера), чтобы prod [i] был равен произведению всех элементов arr [], кроме arr [i]. Решите это без оператора деления и в O (n) .

Пример :
arr [] = {10, 3, 5, 6, 2}
prod [] = {180, 600, 360, 300, 900}

Алгоритм:
1) Создайте временный массив left [] так, чтобы left [i] содержал произведение всех элементов слева от arr [i], за исключением arr [i].
2) Создайте еще один временный массив right [] так, чтобы right [i] содержал произведение всех элементов справа от arr [i], за исключением arr [i].
3) Чтобы получить прод [], умножьте влево [] и вправо [].

Реализация:

C ++

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

using namespace std;

  
/ * Функция для печати массива товаров для данного массива
обр [] размера n * /

void productArray(int arr[], int n)

{

  

    // Базовый вариант

    if (n == 1) {

        cout << 0;

        return;

    }

    / * Выделить память для временных массивов left [] и right [] * /

    int* left = new int[sizeof(int) * n];

    int* right = new int[sizeof(int) * n];

  

    / * Выделить память для массива продуктов * /

    int* prod = new int[sizeof(int) * n];

  

    int i, j;

  

    / * Самый левый элемент левого массива всегда равен 1 * /

    left[0] = 1;

  

    / * Самый правый элемент правого массива всегда равен 1 * /

    right[n - 1] = 1;

  

    / * Построить левый массив * /

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

        left[i] = arr[i - 1] * left[i - 1];

  

    / * Построить правильный массив * /

    for (j = n - 2; j >= 0; j--)

        right[j] = arr[j + 1] * right[j + 1];

  

    / * Построить массив продуктов, используя

        Лево и право[] */

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

        prod[i] = left[i] * right[i];

  

    / * распечатать построенный массив prod * /

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

        cout << prod[i] << " ";

  

    return;

}

  
/ * Код водителя * /

int main()

{

    int arr[] = { 10, 3, 5, 6, 2 };

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

    cout << "The product array is: \n";

    productArray(arr, n);

}

  
// Это код, предоставленный rathbhupendra

С

#include <stdio.h>
#include <stdlib.h>

  
/ * Функция для печати массива товаров для данного массива
обр [] размера n * /

void productArray(int arr[], int n)

{

  

    // Базовый вариант

    if (n == 1) {

        printf("0");

        return;

    }

  

    / * Выделить память для временных массивов left [] и right [] * /

    int* left = (int*)malloc(sizeof(int) * n);

    int* right = (int*)malloc(sizeof(int) * n);

  

    / * Выделить память для массива продуктов * /

    int* prod = (int*)malloc(sizeof(int) * n);

  

    int i, j;

  

    / * Самый левый элемент левого массива всегда равен 1 * /

    left[0] = 1;

  

    / * Самый правый элемент правого массива всегда равен 1 * /

    right[n - 1] = 1;

  

    / * Построить левый массив * /

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

        left[i] = arr[i - 1] * left[i - 1];

  

    / * Построить правильный массив * /

    for (j = n - 2; j >= 0; j--)

        right[j] = arr[j + 1] * right[j + 1];

  

    / * Построить массив продуктов, используя

    Лево и право[] */

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

        prod[i] = left[i] * right[i];

  

    / * распечатать построенный массив prod * /

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

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

  

    return;

}

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

int main()

{

    int arr[] = { 10, 3, 5, 6, 2 };

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

    printf("The product array is: \n");

    productArray(arr, n);

    getchar();

}

Джава

class ProductArray {

    / * Функция для печати массива товаров для данного массива

    обр [] размера n * /

    void productArray(int arr[], int n)

    {

  

        // Базовый вариант

        if (n == 1) {

            System.out.print(0);

            return;

        }

        // Инициализируем память для всех массивов

        int left[] = new int[n];

        int right[] = new int[n];

        int prod[] = new int[n];

  

        int i, j;

  

        / * Самый левый элемент левого массива всегда равен 1 * /

        left[0] = 1;

  

        / * Самый правый элемент правого массива всегда равен 1 * /

        right[n - 1] = 1;

  

        / * Построить левый массив * /

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

            left[i] = arr[i - 1] * left[i - 1];

  

        / * Построить правильный массив * /

        for (j = n - 2; j >= 0; j--)

            right[j] = arr[j + 1] * right[j + 1];

  

        / * Построить массив продуктов, используя

        Лево и право[] */

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

            prod[i] = left[i] * right[i];

  

        / * распечатать построенный массив prod * /

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

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

  

        return;

    }

  

    / * Драйверная программа для проверки функции aboe * /

    public static void main(String[] args)

    {

        ProductArray pa = new ProductArray();

        int arr[] = { 10, 3, 5, 6, 2 };

        int n = arr.length;

        System.out.println("The product array is : ");

        pa.productArray(arr, n);

    }

}

  
// Этот код предоставлен Mayank Jaiswal

python3

# Python реализация вышеуказанного подхода

  
# Функция для печати массива товаров для данного массива
# arr [] размера n

  

  

def productArray(arr, n): 

  

    # Базовый вариант

    if(n == 1):

        print(0)

        return

          

    # Выделите память для временных массивов left [] и right []

    left = [0]*

    right = [0]*

  

    # Выделить память для массива товаров

    prod = [0]*

  

    # Самый левый элемент левого массива всегда равен 1

    left[0] = 1

  

    # Самый правый элемент правого массива всегда равен 1

    right[n - 1] = 1

  

    # Построить левый массив

    for i in range(1, n): 

        left[i] = arr[i - 1] * left[i - 1

  

    # Построить правильный массив

    for j in range(n-2, -1, -1): 

        right[j] = arr[j + 1] * right[j + 1

  

    # Построить массив товаров, используя

    # Лево и право[]

    for i in range(n): 

        prod[i] = left[i] * right[i] 

  

    # распечатать построенный массив prod

    for i in range(n): 

        print(prod[i], end =' '

  

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

arr = [10, 3, 5, 6, 2

n = len(arr) 

print("The product array is:"

productArray(arr, n) 

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

C #

using System;

  

class GFG {

  

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

    для заданного массива arr [] размера n * /

    static void productArray(int[] arr, int n)

    {

  

        // Базовый вариант

        if (n == 1) {

            Console.Write(0);

            return;

        }

        // Инициализируем память для всех массивов

        int[] left = new int[n];

        int[] right = new int[n];

        int[] prod = new int[n];

  

        int i, j;

  

        / * Самый левый элемент левого массива

        всегда 1 * /

        left[0] = 1;

  

        / * Самый правый элемент справа

        массив всегда 1 * /

        right[n - 1] = 1;

  

        / * Построить левый массив * /

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

            left[i] = arr[i - 1] * left[i - 1];

  

        / * Построить правильный массив * /

        for (j = n - 2; j >= 0; j--)

            right[j] = arr[j + 1] * right[j + 1];

  

        / * Построить массив продуктов, используя

        Лево и право[] */

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

            prod[i] = left[i] * right[i];

  

        / * распечатать построенный массив prod * /

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

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

  

        return;

    }

  

    / * Драйверная программа для проверки функции aboe * /

    public static void Main()

    {

        int[] arr = { 10, 3, 5, 6, 2 };

        int n = arr.Length;

        Console.Write("The product array is :\n");

  

        productArray(arr, n);

    }

}

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

PHP

<?php 
// Функция для печати товара
// массив для данного массива
// arr [] размера n

function productArray($arr, $n

  

    // Базовый вариант

    if($n == 1) {

        echo "0";

        return;

    }

    // Инициализация памяти

    // ко всем массивам

    $left = array(); 

    $right = array(); 

    $prod = array(); 

  

    $i; $j

  

    // Самый левый элемент

    // левый массив всегда 1

    $left[0] = 1; 

  

    // Самый правый элемент

    // правый массив всегда 1

    $right[$n - 1] = 1; 

  

    // Построить левый массив

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

        $left[$i] = $arr[$i - 1] * 

                    $left[$i - 1]; 

  

    // Построить правильный массив

    for ($j = $n - 2; $j >= 0; $j--) 

        $right[$j] = $arr[$j + 1] * 

                    $right[$j + 1]; 

  

    // Построить массив продуктов

    // используя left [] и right []

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

        $prod[$i] = $left[$i] * 

                    $right[$i]; 

  

    // выводим построенный массив prod

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

        echo $prod[$i], " "

  

    return

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

$arr = array(10, 3, 5, 6, 2); 

$n = count($arr); 

echo "The product array is : \n"

productArray($arr, $n); 

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


Выход :

The product array is : 
180 600 360 300 900 

Сложность времени: O (n)
Космическая сложность: O (n)
Вспомогательное пространство: O (n)

Вышеуказанный способ может быть оптимизирован для работы в пространстве сложности O (1) . Спасибо Dileep за предложенное ниже решение.

C ++

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

using namespace std;

  
/ * Функция для печати массива товаров
для заданного массива arr [] размера n * /

void productArray(int arr[], int n)

{

  

    // Базовый вариант

    if (n == 1) {

        cout << 0;

        return;

    }

  

    int i, temp = 1;

  

    / * Выделить память для массива продуктов * /

    int* prod = new int[(sizeof(int) * n)];

  

    / * Инициализировать массив продуктов как 1 * /

    memset(prod, 1, n);

  

    / * В этом цикле переменная temp содержит произведение

       элементы слева, кроме arr [i] * /

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

        prod[i] = temp;

        temp *= arr[i];

    }

  

    / * Инициализировать темп 1

    для продукта на правой стороне * /

    temp = 1;

  

    / * В этом цикле переменная temp содержит произведение

       элементы справа, исключая arr [i] * /

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

        prod[i] *= temp;

        temp *= arr[i];

    }

  

    / * распечатать построенный массив prod * /

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

        cout << prod[i] << " ";

  

    return;

}

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

int main()

{

    int arr[] = { 10, 3, 5, 6, 2 };

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

    cout << "The product array is: \n";

    productArray(arr, n);

}

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

Джава

class ProductArray {

    void productArray(int arr[], int n)

    {

  

        // Базовый вариант

        if (n == 1) {

            System.out.print("0");

            return;

        }

  

        int i, temp = 1;

  

        / * Выделить память для массива продуктов * /

        int prod[] = new int[n];

  

        / * Инициализировать массив продуктов как 1 * /

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

            prod[j] = 1;

  

        / * В этом цикле переменная temp содержит произведение

           элементы слева, кроме arr [i] * /

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

            prod[i] = temp;

            temp *= arr[i];

        }

  

        / * Инициализировать temp на 1 для продукта на правой стороне * /

        temp = 1;

  

        / * В этом цикле переменная temp содержит произведение

           элементы справа, исключая arr [i] * /

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

            prod[i] *= temp;

            temp *= arr[i];

        }

  

        / * распечатать построенный массив prod * /

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

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

  

        return;

    }

  

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

    public static void main(String[] args)

    {

        ProductArray pa = new ProductArray();

        int arr[] = { 10, 3, 5, 6, 2 };

        int n = arr.length;

        System.out.println("The product array is : ");

        pa.productArray(arr, n);

    }

}

  
// Этот код предоставлен Mayank Jaiswal

python3

# Программа Python3 для головоломки Product Array

def productArray(arr, n):

  

    # Базовый вариант

    if n == 1:

        print(0)

        return

  

    i, temp = 1, 1

  

    # Выделить память для массива товаров

    prod = [1 for i in range(n)]

  

    # Инициализировать массив продукта как 1

  

    # В этом цикле переменная temp содержит произведение

    # элементов на левой стороне, исключая arr [i]

    for i in range(n):

        prod[i] = temp

        temp *= arr[i]

  

    # Инициализировать темп до 1 для продукта на правой стороне

    temp = 1

  

    # В этом цикле переменная temp содержит произведение

    # элементов на правой стороне, исключая arr [i]

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

        prod[i] *= temp

        temp *= arr[i]

  

    # Распечатать построенный массив prod

    for i in range(n):

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

  

    return

  
Код водителя

arr = [10, 3, 5, 6, 2]

n = len(arr)

print("The product array is: n")

productArray(arr, n)

  
# Этот код предоставлен Мохит Кумар

C #

using System;

  

class GFG {

  

    static void productArray(int[] arr, int n)

    {

  

        // Базовый вариант

        if (n == 1) {

            Console.Write(0);

            return;

        }

        int i, temp = 1;

  

        / * Выделить память для продукта

        массив * /

        int[] prod = new int[n];

  

        / * Инициализировать массив продуктов как 1 * /

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

            prod[j] = 1;

  

        / * В этом цикле переменная temp содержит

        произведение элементов на левой стороне

        исключая обр [я] * /

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

            prod[i] = temp;

            temp *= arr[i];

        }

  

        / * Инициализировать temp на 1 для продукта на

        правая сторона */

        temp = 1;

  

        / * В этом цикле переменная temp содержит

        произведение элементов на правой стороне

        исключая обр [я] * /

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

            prod[i] *= temp;

            temp *= arr[i];

        }

  

        / * распечатать построенный массив prod * /

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

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

  

        return;

    }

  

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

    public static void Main()

    {

        int[] arr = { 10, 3, 5, 6, 2 };

        int n = arr.Length;

        Console.WriteLine("The product array is : ");

  

        productArray(arr, n);

    }

}

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

PHP

<?php
// PHP программа для
// Продуктовая головоломка

      

function productArray($arr, $n

    {

  

        // Базовый вариант

        if ($n == 1) {

            echo "0";

            return;

        }

        $i; $temp = 1;

          

        / * Выделить память для

           массив продуктов * /

        $prod = array();

  

        / * Инициализировать продукт

           массив как 1 * /

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

            $prod[$j] = 1;

  

        / * В этом цикле temp

           переменная содержит

           произведение элементов

           на левой стороне

           исключая обр [я] * /

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

        {

            $prod[$i] = $temp;

            $temp *= $arr[$i];

        }

  

        / * Инициализировать темп 1

           для продукта справа

           боковая сторона */

        $temp = 1;

  

        / * В этом цикле temp

           переменная содержит

           произведение элементов

           на правой стороне

           исключая обр [я] * /

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

        {

            $prod[$i] *= $temp;

            $temp *= $arr[$i];

        }

  

        / * распечатать построенный

           массив prod * /

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

            echo $prod[$i], " ";

  

        return;

    }

  

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

        $arr = array(10, 3, 5, 6, 2);

        $n = count($arr);

        echo "The product array is : \n";

        productArray($arr, $n);

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


Выход :

The product array is : 
180 600 360 300 900 

Сложность времени: O (n)
Космическая сложность: O (n)
Вспомогательное пространство: O (1)


Головоломка с массивом продуктов Набор 2 (O (1) пробел)

Связанная проблема:
Построить массив из XOR всех элементов массива, кроме элемента с тем же индексом

Пожалуйста, пишите комментарии, если вы обнаружите, что приведенный выше код / алгоритм неверен, или найдете лучшие способы решения той же проблемы.

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

Головоломка с массивом продуктов

0.00 (0%) 0 votes