ភាពខុសគ្នាដែលអាចកើតមានអតិបរមានៃសំណុំរងពីរនៃអារេមួយ


កម្រិតលំបាក រឹង
សួរញឹកញាប់ Atlassian Cadence ឥណ្ឌា Directi FreeCharge ល្ខោនអូប៉េរ៉ា PayU Snapchat អ៊ិនធឺណិតដង។ Xome
អារេ ហាស់ តម្រៀប

ឧបមាថាយើងមាន integer អារេ។ សេចក្តីថ្លែងការណ៍បញ្ហា“ ភាពខុសគ្នាដែលអាចកើតមានអតិបរមានៃសំណុំរងពីរនៃអារេ” ស្នើឱ្យស្វែងយល់ពីភាពខុសគ្នាអតិបរមាដែលអាចកើតមានរវាងសំណុំរងទាំងពីរនៃអារេមួយ។

លក្ខខណ្ឌដែលត្រូវអនុវត្តតាម៖

  • អារេមួយអាចផ្ទុកនូវធាតុដដែលៗប៉ុន្តែប្រេកង់ខ្ពស់បំផុតនៃធាតុមួយមិនគួរធំជាង ២ ទេ។
  • អ្នកគួរតែបង្កើតសំណុំរងពីរដូច្នេះភាពខុសគ្នារវាងផលបូកនៃធាតុនីមួយៗគឺអតិបរមា។
  • ធាតុទាំងអស់នៃអារេគួរតែត្រូវបានបែងចែករវាងសំណុំរងទាំងពីរដោយមិនបន្សល់ទុកធាតុណាមួយឡើយ។
  • ធាតុពីរមិនគួរដូចគ្នានៅក្នុងសំណុំរង។

ឧទាហរណ៍

ភាពខុសគ្នាដែលអាចកើតមានអតិបរមានៃសំណុំរងពីរនៃអារេមួយ

arr[] = {2, 5, -3, -1, 5, 7}
13

ការពន្យល់

សំណុំរង→ (២, ៧, ៥) - (-៣, ១, ៥) = ១៣

{1, 5, 3, -1, -5, 6}
21

ការពន្យល់

សំណុំរង→ (១, ៣, ៥, ៦) - (-៥, ១) = ២១

ក្បួនដោះស្រាយ

  1. ប្រកាសពីរ ផែនទី, មួយសម្រាប់វិជ្ជមាននិងមួយសម្រាប់ធាតុអវិជ្ជមាន។
  2. រក្សាទុកធាតុវិជ្ជមាននិងការរាប់របស់វានៅក្នុងផែនទីមួយ។
  3. បន្តបន្ថែមធាតុវិជ្ជមានទាំងអស់ដែលមានប្រេកង់ 1 និងរក្សាទុកវា សំណុំរង ១.
  4. រក្សាទុកធាតុអវិជ្ជមាននិងការរាប់របស់វានៅក្នុងផែនទីមួយទៀត។
  5. បន្តបន្ថែមរាល់ចំនុចអវិជ្ជមានទាំងអស់ដែលមានប្រេកង់ទី ១ និងរក្សាទុកវា សំណុំរង ១.
  6. ត្រឡប់ subset1-subset2 ។

ការពន្យល់

យើងបានផ្តល់ឱ្យ អារេយើងត្រូវស្វែងយល់ពីភាពខុសគ្នារវាងផលបូកនៃធាតុផ្សំនៃសំណុំរងពីរហើយនោះគួរតែជាអតិបរមា។ យើងនឹងប្រើក ផែនទី. ហាសហាស។ ផ្តល់នូវវិធីដ៏មានប្រសិទ្ធិភាពដើម្បីដោះស្រាយសំណួរនេះ។ យើងនឹងប្រើផែនទីពីរ។ មួយគឺសម្រាប់ប្រតិបត្តិការដែលបានធ្វើលើធាតុវិជ្ជមាននិងមួយទៀតសម្រាប់ធាតុអវិជ្ជមាន។ អារេអាចមានធាតុវិជ្ជមាននិងអវិជ្ជមានទាំងពីរដូច្នេះយើងក៏ត្រូវដោះស្រាយរឿងនោះដែរ។

យើងនឹងយកអារេនិងផែនទី។ យើងនឹងជ្រើសរើសធាតុនីមួយៗនៃអារេហើយពិនិត្យមើលថាតើវាធំជាង ០ ។ បន្ទាប់មកយើងនឹងរក្សាទុកវានៅក្នុងផែនទីជាមួយនឹងចំនួននៃការកើតឡើង។ បន្ទាប់ពីរក្សាទុកប្រេកង់នៃធាតុវិជ្ជមានយើងនឹងបន្ថែមគុណតម្លៃទាំងអស់នៃអារេដែលធំជាង ០ និងមានប្រេកង់ត្រឹមតែ ១ មានន័យថាយើងត្រូវមិនអើពើនឹងធាតុទាំងនោះដែលកើតឡើងច្រើនដងឬច្រើនជាងនេះ។

រឿងដដែលនឹងធ្វើជាមួយធាតុអវិជ្ជមានយើងនឹងជ្រើសរើសរាល់ធាតុទាំងអស់នៃអារេហើយពេលនេះយើងនឹងពិនិត្យមើលថាតើវាតិចជាង ០ ។ យើងនឹងទុកវានៅក្នុងផែនទី (ធ្វើវាជាលេខវិជ្ជមាន) ជាមួយចំនួនរបស់វា ការកើតឡើង។ បន្ទាប់ពីរក្សាទុកប្រេកង់នៃធាតុអវិជ្ជមានយើងនឹងបន្ថែមគុណតម្លៃទាំងអស់នៃអារេដែលតិចជាង ០ និងមានប្រេកង់ត្រឹមតែ ១ ។ នៅទីនេះផងដែរយើងត្រូវមិនអើពើនឹងធាតុទាំងនោះដែលកើតឡើងច្រើនដងរឺច្រើនជាងនេះ។ ជាងម្តង។

បន្ទាប់ពីទទួលបានផលបូកនៃលក្ខខណ្ឌធាតុវិជ្ជមាននិងអវិជ្ជមានទាំងអស់ធ្វើតាមធាតុដែលមានប្រេកង់ទី ១ យើងត្រូវត្រឡប់ផលបូកនៃផលបូកទាំងពីរហើយនោះជាចម្លើយរបស់យើង។

លេខកូដ

កូដ C ++ ដើម្បីស្វែងរកភាពខុសគ្នាអតិបរមាដែលអាចកើតមាននៃសំណុំរងពីរនៃអារេមួយ

#include<iostream>
#include<unordered_map>

using namespace std;

int maxDiff(int arr[], int n)
{
    unordered_map<int, int> positiveElement;
    unordered_map<int, int> negativeElement;

    int sumSubset1 = 0, sumSubset2 = 0;
    for (int i = 0; i <= n - 1; i++)
        if (arr[i] > 0)
            positiveElement[arr[i]]++;

    for (int i = 0; i <= n - 1; i++)
        if (arr[i] > 0 && positiveElement[arr[i]] == 1)
            sumSubset1 += arr[i];

    for (int i = 0; i <= n - 1; i++)
        if (arr[i] < 0)
            negativeElement[abs(arr[i])]++;

    for (int i = 0; i <= n - 1; i++)
        if (arr[i] < 0 &&
                negativeElement[abs(arr[i])] == 1)
            sumSubset2 += arr[i];

    return abs(sumSubset1 - sumSubset2);
}
int main()
{
    int arr[] = {2,5,-3,-1,5,7};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum difference found is: " << maxDiff(arr, n);
    return 0;
}
Maximum difference found is: 13

កូដចាវ៉ាដើម្បីរកភាពខុសគ្នាអតិបរមាដែលអាចធ្វើបាននៃសំណុំរងពីរនៃអារេមួយ

import java.util.HashMap;
class SubsetDifference
{
    public static int getDifference(int arr[], int n)
    {
        HashMap<Integer, Integer> positiveElement=new HashMap<Integer, Integer>();
        HashMap<Integer, Integer> negativeElement=new HashMap<Integer, Integer>();
        int sumSubset1 = 0, sumSubset2 = 0;
        for (int i = 0; i <= n - 1; i++)
        {
            if (arr[i] > 0)
            {
                if(positiveElement.containsKey(arr[i]))
                    positiveElement.put(arr[i],positiveElement.get(arr[i])+1);
                else
                    positiveElement.put(arr[i],1);
            }
        }
        for (int i = 0; i <= n - 1; i++)
            if (arr[i] > 0 && positiveElement.get(arr[i]) == 1)
                sumSubset1 += arr[i];

        for (int i = 0; i <= n - 1; i++)
        {
            if (arr[i] < 0)
            {
                if(negativeElement.containsKey(Math.abs(arr[i])))
                    negativeElement.put(Math.abs(arr[i]),negativeElement.get(Math.abs(arr[i]))+1);
                else
                    negativeElement.put(Math.abs(arr[i]),1);
            }
        }
        for (int i = 0; i <= n - 1; i++)
            if (arr[i] < 0 && negativeElement.get(Math.abs(arr[i]))== 1)
                sumSubset2 += arr[i];

        return Math.abs(sumSubset1 - sumSubset2);
    }
    public static void main(String [] args)
    {
        int arr[] = {2,5,-3,-1,5,7};
        int n = arr.length;
        System.out.println("Maximum difference found is:"+getDifference(arr, n));
    }
}
Maximum difference found is:13

ការវិភាគស្មុគស្មាញ

ស្មុគស្មាញពេលវេលា

អូរ (n) ដែលជាកន្លែងដែល “ n” គឺជាចំនួនធាតុក្នុងអារេ។ ដោយសារតែយើងបានប្រើហាស់ម៉ាសយើងអាចអនុវត្តការបញ្ចូល / លុប / ស្វែងរកក្នុងអូ (១) ។

ភាពស្មុគស្មាញនៃលំហ

អូរ (n) ដែលជាកន្លែងដែល “ n” គឺជាចំនួនធាតុក្នុងអារេ។