തന്നിരിക്കുന്ന അറേയ്‌ക്കായി എല്ലാ അദ്വിതീയ ഉപ-അറേ തുകയുടെയും തുക കണ്ടെത്തുക  


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ആമസോൺ ഫേസ്ബുക്ക് ഗ്രേ ഓറഞ്ച് Intuit മൈക്രോസോഫ്റ്റ് നാഗാരോ
അറേ ഹാഷ് ക്രമപ്പെടുത്തൽ

നിങ്ങൾക്ക് പൂർണ്ണസംഖ്യകളുടെ ഒരു നിരയുണ്ടെന്ന് കരുതുക. “തന്നിരിക്കുന്ന അറേയ്‌ക്കുള്ള എല്ലാ അദ്വിതീയ ഉപ-അറേ തുകകളുടെ ആകെത്തുക കണ്ടെത്തുക” എന്ന പ്രശ്‌നം എല്ലാ അദ്വിതീയ ഉപ-അറേകളുടെയും തുക കണ്ടെത്താൻ ആവശ്യപ്പെടുന്നു (ഉപ-അറേ തുക എന്നത് ഓരോ ഉപ-അറേയുടെയും ഘടകങ്ങളുടെ ആകെത്തുകയാണ്).

അദ്വിതീയ ഉപ-അറേ തുക പ്രകാരം, ഒരു ഉപ-അറേയ്ക്കും ഒരേ മൂല്യമില്ലെന്ന് പറയാൻ ഞങ്ങൾ ഉദ്ദേശിച്ചു.

ഉദാഹരണം  

arr[] = {3, 1, 4, 5}
44
arr[] = {2,1,3,6}
36

തന്നിരിക്കുന്ന അറേയ്‌ക്കായി എല്ലാ അദ്വിതീയ ഉപ-അറേ തുകയുടെയും തുക കണ്ടെത്തുക  

അൽഗോരിതം  

  1. ഒരു പ്രഖ്യാപിക്കുക ഭൂപടം.
  2. ഗണം ഔട്ട്പുട്ട് ലേക്ക് .
  3. I = 0 മുതൽ i വരെ അറേയിലൂടെ സഞ്ചരിക്കുക
    1. സജ്ജമാക്കുക തുക 0 ലേക്ക്.
    2. അറേ j = i, j ലേക്ക് സഞ്ചരിക്കുക
      • തുകയിലേക്ക് arr [j] ന്റെ മൂല്യം തുകയിലേക്ക് ചേർക്കുക.
      • മാപ്പും അതിന്റെ സംഭവവും മാപ്പിൽ ചേർക്കുക.
  4. മാപ്പ് സഞ്ചരിച്ച് ആ കീയുടെ എൻ‌ട്രികൾ 1 ന്റെ മൂല്യം പരിശോധിക്കുക.
    1. അവസ്ഥ തൃപ്‌തികരമാണെന്ന് കണ്ടെത്തുമ്പോഴെല്ലാം key ട്ട്‌പുട്ടിലേക്ക് കീകളുടെ മൂല്യം ചേർക്കുക.
  5. Return ട്ട്‌പുട്ട് നൽകുന്നു.

വിശദീകരണം

ഞങ്ങൾക്ക് ഒരു നൽകിയിട്ടുണ്ട് പൂർണ്ണസംഖ്യ ശ്രേണി. എല്ലാ അദ്വിതീയ ഉപ-അറേകളുടെയും തുക കണ്ടെത്തുക എന്നതാണ് ഞങ്ങളുടെ ചുമതല. ഓരോ ഉപ-അറേയുടെയും തുക ഓരോ ഉപ-അറേയുടെ ഘടകത്തിന്റെയും ആകെത്തുകയായിരിക്കും. ഞങ്ങൾ ഉപയോഗിക്കാൻ പോകുന്നു ഹാഷിംഗ് ഈ ചോദ്യം പരിഹരിക്കാൻ. I ന്റെ മൂല്യം മാറ്റുമ്പോഴെല്ലാം ഞങ്ങൾ ഒരു അറേയുടെ ഓരോ ഘടകങ്ങളും എടുത്ത് തുക 0 ആയി ആരംഭിക്കും. ആന്തരിക ലൂപ്പിൽ പ്രവേശിക്കുമ്പോൾ, അതിൽ നിന്ന് ഒരു ശ്രേണി ഞങ്ങൾ സഞ്ചരിക്കും i ലേക്ക് n, അറേയുടെയും തുകയുടെയും ഓരോ മൂല്യവും ചേർക്കുന്നു. തുകയും അതിന്റെ സംഭവവും ഞങ്ങൾ ഒരേസമയം മാപ്പിൽ സംഭരിക്കുന്നു. മുഴുവൻ അറേയും സന്ദർശിച്ച ശേഷം, സാധ്യമായ എല്ലാ ഉപ-അറേകളും കണ്ടെത്തുക. അതിനുശേഷം, മാപ്പിൽ ഒരു തവണ മാത്രം സംഭവിക്കുന്ന തുകകൾക്കായി ഞങ്ങൾ തിരയുന്നു. അദ്വിതീയ ഉപ-അറേകളുടെ ആകെത്തുക ഞങ്ങൾക്ക് ആവശ്യമുള്ളതിനാൽ, വ്യത്യസ്തമായ തുകകളുള്ള അർത്ഥം. അതിനാൽ, മാപ്പിൽ ഒരു തവണ സംഭവിക്കുന്ന തുക കണ്ടെത്തുമ്പോൾ, ആരുടെ ആവൃത്തി 1 ആണെന്ന് പറയാൻ ഉദ്ദേശിച്ചാൽ, ആ തുകകളുടെ മൂല്യം ഞങ്ങൾ .ട്ട്‌പുട്ടിൽ ചേർത്ത് അപ്‌ഡേറ്റ് ചെയ്യും.

ഇതും കാണുക
ലെവൽ ഓർഡർ സർപ്പിള രൂപത്തിൽ സഞ്ചരിക്കുന്നു

അതിനുള്ള ഒരു ഉദാഹരണം പരിഗണിക്കുക:

ഉദാഹരണം

arr [] = {3, 1, 4, 5}

ആദ്യം, നമുക്ക് i = 0 ഉണ്ട്, പിന്നെ നമുക്ക് ഒരു ഘടകമായി 3 ഉണ്ട്, ഞങ്ങൾ 3 ൽ നിന്ന് ആരംഭിക്കും, ഞങ്ങൾ തുകയിലേക്ക് 3 ചേർത്ത് 3 മാപ്പിലേക്ക് അപ്ഡേറ്റ് ചെയ്യും, തുടർന്ന് തുകയിലേക്ക് 1 ചേർത്ത് 4 മാപ്പിലേക്ക് അപ്ഡേറ്റ് ചെയ്യുന്നു , തുടർന്ന് തുകയിലേക്ക് ഒരു ഘടകമായി 4 എടുത്ത് മാപ്പിൽ 7 ചേർക്കുക. ഈ രീതിയിൽ, 5 സന്ദർശിച്ച് മാപ്പിലേക്ക് 12 അപ്‌ഡേറ്റുചെയ്‌തതിനുശേഷം ഞങ്ങൾ ആദ്യത്തെ യാത്ര അവസാനിപ്പിക്കും.

അതിനാൽ, 4 നെ ഒരു ഘടകമായി എടുത്ത് 4 മുതൽ ആരംഭിക്കുമ്പോൾ, തുക ഇതിനകം മാപ്പിലേക്ക് അപ്‌ഡേറ്റ് ചെയ്യും, കാരണം 4 ഇതിനകം തന്നെ ഭൂപടം, ഞങ്ങൾ അതിന്റെ ആവൃത്തി വർദ്ധിപ്പിക്കും, കൂടാതെ ആവൃത്തി 1 അല്ലാത്ത തുകകളെ ഞങ്ങൾ അവഗണിക്കും. ഈ രീതിയിൽ, ഞങ്ങൾക്ക് അദ്വിതീയ ഉപ-അറേകൾ കൈകാര്യം ചെയ്യാൻ കഴിയും.

കോഡ്  

തന്നിരിക്കുന്ന അറേയ്‌ക്കുള്ള എല്ലാ അദ്വിതീയ ഉപ-അറേ തുകകളുടെയും തുക കണ്ടെത്തുന്നതിന് സി ++ കോഡ്

#include<iostream>
#include<unordered_map>

using namespace std;

int findSumOfUnique(int arr[], int n)
{
    int output = 0;
    unordered_map<int, int> MAP;

    for (int i = 0; i < n; i++)
    {
        int sum = 0;
        for (int j = i; j < n; j++)
        {
            sum += arr[j];
            MAP[sum]++;
        }
    }
    for (auto entry : MAP)
        if (entry.second == 1)
            output += entry.first;

    return output;
}
int main()
{
    int arr[] = { 3, 1, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << findSumOfUnique(arr, n);
    return 0;
}
44

തന്നിരിക്കുന്ന അറേയ്‌ക്കുള്ള എല്ലാ അദ്വിതീയ ഉപ-അറേ തുകകളുടെയും തുക കണ്ടെത്താനുള്ള ജാവ കോഡ്

import java.util.HashMap;
import java.util.Map;

class SumUniqueSubArray
{
    public static int findSumOfUnique(int []arr, int n)
    {
        int output = 0;

        HashMap<Integer,Integer> MAP = new HashMap<Integer,Integer>();
        for (int i = 0; i < n; i++)
        {
            int sum = 0;
            for (int j = i; j < n; j++)
            {
                sum += arr[j];
                if (MAP.containsKey(sum))
                {
                    MAP.put(sum, MAP.get(sum) + 1);
                }
                else
                {
                    MAP.put(sum, 1);
                }
            }
        }
        for (Map.Entry<Integer,Integer> entry : MAP.entrySet())
            if (entry.getValue() == 1)
                output += entry.getKey();

        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = {3, 1, 4, 5};
        int n = arr.length;
        System.out.println(findSumOfUnique(arr, n));
    }
}
44

സങ്കീർണ്ണത വിശകലനം  

സമയ സങ്കീർണ്ണത

O (n2എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം. കാരണം ഞങ്ങൾ 2 നെസ്റ്റഡ് ലൂപ്പുകൾ ഉപയോഗിക്കുകയും തുക തിരയുന്നത് ഹാഷ്‌മാപ്പ് ഉപയോഗിച്ച് O (1) ൽ നടത്തുകയും ചെയ്യുന്നു.

ഇതും കാണുക
തന്നിരിക്കുന്ന സംഖ്യയ്ക്ക് തുല്യമായ ഉൽപ്പന്നമുള്ള ട്രിപ്പിളുകളുടെ എണ്ണം എണ്ണുക

ബഹിരാകാശ സങ്കീർണ്ണത

O (n ^ 2) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം. കാരണം ഏറ്റവും മോശം അവസ്ഥയിൽ നമുക്ക് n ^ 2 വ്യത്യസ്ത ഉപ-അറേ തുക ഉണ്ടായിരിക്കാം.