Рубрики

Количество секступлетов (или шесть значений), которые удовлетворяют уравнению

Дан массив из n элементов. Задача состоит в том, чтобы найти количество секступлетов, которые удовлетворяют приведенному ниже уравнению, так чтобы a, b, c, d, e и f принадлежали данному массиву

a * b + c - e = f
    d

Примеры:

Input :  arr[] = { 1 }.
Output : 1
a = b = c = d = e = f = 1 satisfy
the equation.

Input :  arr[] = { 2, 3 }
Output : 4

Input :  arr[] = { 1, -1 }
Output : 24

Во-первых, переупорядочьте уравнение, a * b + c = (f + e) * d.
Теперь создайте два массива, один для LHS (левая сторона) уравнения и один для RHS (правая сторона) уравнения. Поиск каждого элемента массива RHS в массиве LHS. Всякий раз, когда вы найдете значение RHS в LHS, проверьте, сколько раз оно повторяется в LHS, и добавьте это количество к общему. Поиск может быть выполнен с использованием бинарного поиска, путем сортировки массива LHS.

Ниже приведена реализация этого подхода:

C ++

// C ++ программа для подсчета 6 значений из массива
// которые удовлетворяют уравнению с 6 переменными
#include<bits/stdc++.h>

using namespace std;

  
// Возвращает количество из 6 значений из arr []
// которые удовлетворяют уравнению с 6 переменными

int findSextuplets(int arr[], int n)

{

    // Генерация возможных значений RHS уравнения

    int index = 0;

    int RHS[n*n*n + 1];

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

      if (arr[i])  // Проверка d должна быть ненулевой

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

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

            RHS[index++] = arr[i] * (arr[j] + arr[k]);

  

    // Сортировка RHS [], чтобы мы могли выполнять бинарный поиск в нем.

    sort(RHS, RHS + n);

  

    // Генерация всех возможных значений LHS уравнения

    // и нахождение количества вхождений значения в RHS.

    int result = 0;

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

    {

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

        {

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

            {

                int val = arr[i] * arr[j] + arr[k];

                result += (upper_bound(RHS, RHS + index, val) -

                          lower_bound(RHS, RHS + index, val));

            }

        }

    }

  

    return result;

}

  
// Управляемая программа

int main()

{

    int arr[] = {2, 3};

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

  

    cout << findSextuplets(arr, n) << endl;

    return 0;

}

Джава

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

import java.util.Arrays; 

class GFG{

static int upper_bound(int[] array, int length, int value) {

        int low = 0;

        int high = length;

        while (low < high) {

            final int mid = (low + high) / 2;

            if (value >= array[mid]) {

                low = mid + 1;

            } else {

                high = mid;

            }

        }

        return low;

    }

  static int lower_bound(int[] array, int length, int value) {

        int low = 0;

        int high = length;

        while (low < high) {

            final int mid = (low + high) / 2;

            if (value <= array[mid]) {

                high = mid;

            } else {

                low = mid + 1;

            }

        }

        return low;

    }  

static int findSextuplets(int[] arr, int n)

{

    // Генерация возможных значений RHS уравнения

    int index = 0;

    int[] RHS = new int[n * n * n + 1];

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

    {

      if (arr[i] != 0) // Проверка d должна быть ненулевой

      {

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

        {

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

          {

            RHS[index++] = arr[i] * (arr[j] + arr[k]);

          }

        }

      }

    }

  

    // Сортировка RHS [], чтобы мы могли выполнять бинарный поиск в нем.

    Arrays.sort(RHS);

  

    // Генерация всех возможных значений LHS уравнения

    // и нахождение количества вхождений значения в RHS.

    int result = 0;

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

    {

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

        {

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

            {

                int val = arr[i] * arr[j] + arr[k];

                result += (upper_bound(RHS, index, val)-lower_bound(RHS, index, val));

            }

        }

    }

  

    return result;

}

  
// Управляемая программа

public static void main(String[] args)

{

    int[] arr = {2, 3};

    int n = arr.length;

  

    System.out.println(findSextuplets(arr, n));

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

python3

# Python3 программа для подсчета 6 значений
# из массива, который удовлетворяет уравнению
# с 6 переменными

  

def upper_bound(array, length, value):

    low = 0;

    high = length;

    while (low < high):

        mid = int((low + high) / 2);

        if (value >= array[mid]):

                low = mid + 1;

        else:

            high = mid;

          

    return low;

      

def lower_bound(array, length, value):

    low = 0;

    high = length;

    while (low < high):

        mid = int((low + high) / 2);

        if (value <= array[mid]):

            high = mid;

        else:

            low = mid + 1;

    return low;

      

def findSextuplets(arr, n):

  

    # Генерация возможных значений

    # RHS уравнения

    index = 0;

    RHS = [0] * (n * n * n + 1);

      

    for i in range(n):

        if (arr[i] != 0):

              

            # Проверка d должна быть ненулевой.

            for j in range(n):

                for k in range(n):

                    RHS[index] = arr[i] * (arr[j] + 

                                           arr[k]);

                    index += 1;

  

    # Сортировать RHS [], чтобы мы могли сделать

    # бинарный поиск в нем.

    RHS.sort();

  

    # Генерация всех возможных значений

    # LHS уравнения и нахождение

    # количество вхождений значения в RHS.

    result = 0;

    for i in range(n):

        for j in range(n):

            for k in range(n):

                val = arr[i] * arr[j] + arr[k];

                result += (upper_bound(RHS, index, val) -

                           lower_bound(RHS, index, val));

  

    return result;

  
Код водителя

arr = [2, 3];

n = len(arr);

  

print(findSextuplets(arr, n));

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

C #

// C # программа для подсчета 6 значений из массива
// которые удовлетворяют уравнению с 6 переменными

using System;

using System.Collections;

  

class GFG{

static int upper_bound(int[] array, int length, int value) {

        int low = 0;

        int high = length;

        while (low < high) {

            int mid = (low + high) / 2;

            if (value >= array[mid]) {

                low = mid + 1;

            } else {

                high = mid;

            }

        }

        return low;

    }

static int lower_bound(int[] array, int length, int value) {

        int low = 0;

        int high = length;

        while (low < high) {

            int mid = (low + high) / 2;

            if (value <= array[mid]) {

                high = mid;

            } else {

                low = mid + 1;

            }

        }

        return low;

    

static int findSextuplets(int[] arr, int n)

{

    // Генерация возможных значений RHS уравнения

    int index = 0;

    int[] RHS = new int[n * n * n + 1];

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

    {

    if (arr[i] != 0) // Проверка d должна быть ненулевой

    {

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

        {

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

        {

            RHS[index++] = arr[i] * (arr[j] + arr[k]);

        }

        }

    }

    }

  

    // Сортировка RHS [], чтобы мы могли выполнять бинарный поиск в нем.

    Array.Sort(RHS);

  

    // Генерация всех возможных значений LHS уравнения

    // и нахождение количества вхождений значения в RHS.

    int result = 0;

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

    {

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

        {

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

            {

                int val = arr[i] * arr[j] + arr[k];

                result += (upper_bound(RHS, index, val)-lower_bound(RHS, index, val));

            }

        }

    }

  

    return result;

}

  
// Управляемая программа

static void Main()

{

    int[] arr = {2, 3};

    int n = arr.Length;

  

    Console.WriteLine(findSextuplets(arr, n));

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

PHP

<?php
// PHP программа для подсчета 6 значений из
// массив, который удовлетворяет уравнению
// с 6 переменными

  

function upper_bound($array, $length, $value)

{

    $low = 0;

    $high = $length;

    while ($low < $high)

    {

        $mid = (int)(($low + $high) / 2);

        if ($value >= $array[$mid])

                $low = $mid + 1;

        else

            $high = $mid;

    }

    return $low;

}

  

function lower_bound($array, $length, $value)

{

    $low = 0;

    $high = $length;

    while ($low < $high)

    {

        $mid = (int)(($low + $high) / 2);

        if ($value <= $array[$mid])

            $high = $mid;

        else

            $low = $mid + 1;

    }

    return $low;

}

  
// Возвращает количество из 6 значений из arr []
// которые удовлетворяют уравнению с 6 переменными

function findSextuplets($arr, $n)

{

    // Генерация возможных значений

    // RHS уравнения

    $index = 0;

    $RHS = array_fill(0, $n * $n * $n + 1, 0);

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

    if ($arr[$i] != 0) // Проверка d должна быть ненулевой

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

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

            $RHS[$index++] = $arr[$i] * 

                            ($arr[$j] + $arr[$k]);

  

    // Сортировка RHS [], чтобы мы могли сделать

    // бинарный поиск в нем.

    sort($RHS);

  

    // Генерируем все возможные значения LHS

    // уравнения и нахождения числа

    // вхождения значения в RHS.

    $result = 0;

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

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

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

            {

                $val = $arr[$i] * $arr[$j] + $arr[$k];

                $result += (upper_bound($RHS, $index, $val) - 

                            lower_bound($RHS, $index, $val));

            }

  

    return $result;

}

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

$arr = array(2, 3);

$n = count($arr);

  

print(findSextuplets($arr, $n));

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


Выход:

4

Сложность времени: O (N 3 log N)

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

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

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

Количество секступлетов (или шесть значений), которые удовлетворяют уравнению

0.00 (0%) 0 votes