किसी सरणी में गैर-दोहराए जाने वाले तत्वों (अलग) तत्वों का योग खोजें


कठिनाई स्तर आसान
में अक्सर पूछा ऑक्सिजन वॉलेट
ऐरे हैश hashing छंटाई

समस्या का विवरण

बार-बार तत्वों के साथ एक पूर्णांक सरणी, ए [] को देखते हुए, "सरणी में गैर-दोहराए जाने वाले तत्वों (अलग) तत्वों का योग" समस्या को सरणी में सभी अलग-अलग तत्वों का योग खोजने के लिए कहते हैं। तो, बस उन संख्याओं को जोड़ें जो सरणी में दोहराई नहीं जाती हैं।

उदाहरण

A[]={1, 4, 2, 1, 5, 2, 3, 2}
11

स्पष्टीकरण: दोहराए जाने वाले तत्व हैं: 4, 5, 3. इसलिए उनका योग = 4 + 5 + 3 = 11।

पाशविक बल

किसी सरणी में गैर-दोहराए जाने वाले तत्वों (अलग) तत्वों का योग खोजने के लिए मुख्य विचार

प्रत्येक तत्व के लिए, जांचें कि क्या कोई अन्य तत्व मौजूद है या नहीं जिसका मूल्य समान है और जिसका सूचकांक वर्तमान सूचकांक से कम है। यदि ऐसा कोई तत्व नहीं है, तो वर्तमान तत्व को उत्तर में जोड़ें अन्यथा इसे छोड़ दें।

कलन विधि

1. Run a loop for I in range 0 to n-1 
    1. Run a loop for j in range 0 to i 
        1. If j==i, add A[i]. 
        2. If A[i] is equal to A[j], break out from this loop. 
    2. Return.

कोड

C ++ कोड

#include <bits/stdc++.h>
using namespace std;
void sumOfDistinctElements(vector<int> A)
{
    int n = A.size();
    int sum = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            if (j == i)
            {
                sum += A[i];
            }
            if (A[i] == A[j])
            {
                break;
            }
        }
    }
    cout << "Sum of distinct Elements in the array is: " << sum << endl;
    return;
}
int main()
{
    vector<int> A = {1, 4, 2, 1, 5, 2, 3, 2};
    sumOfDistinctElements(A);
    return 0;
}
Sum of distinct Elements in the array is: 15

जावा कोड

public class Main
{   
    static void sumOfDistinctElements(int A[])
    {
        int n = A.length;
        int sum = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j <= i; j++)
            {
                if (j == i)
                {
                    sum += A[i];
                }
                if (A[i] == A[j])
                {
                    break;
                }
            }
        }
        System.out.println("Sum of distinct Elements in the array is: " + sum);
        return;
    }
  public static void main(String[] args) {
    int A[] = {1, 4, 2, 1, 5, 2, 3, 2};
        sumOfDistinctElements(A);
  }
}
Sum of distinct Elements in the array is: 15

जटिलता विश्लेषण

समय की जटिलता

हमारे पास दो नेस्टेड लूप हैं, प्रत्येक का आकार n। तो समय जटिलता है ओ (एन ^ 2)।

अंतरिक्ष की जटिलता

हम कोई अतिरिक्त स्थान नहीं ले रहे हैं इसलिए अंतरिक्ष की जटिलता है ओ (1).

अनुकूलित दृष्टिकोण

किसी सरणी में गैर-दोहराए जाने वाले तत्वों (अलग) तत्वों का योग खोजने के लिए मुख्य विचार

हम एक हैश तालिका बनाए रखेंगे जो उन तत्वों को संग्रहीत करेगी जो हमने पहले ही मुद्रित किए हैं। तो, हम सरणी को पुन: व्यवस्थित करेंगे, अगर हमें सरणी में एक तत्व मिला है जो हैश तालिका में मौजूद नहीं है तो हम उस तत्व को उत्तर में जोड़ देंगे और उसे हैश तालिका में डाल देंगे, अन्यथा हम उस तत्व को छोड़ देंगे।

कलन विधि

1. Declare a hash table.
2. Run a loop for I in range 0 to n-1:
    1. If A[i] is not present in the hash table, then add it and insert it in the hash table.
    2. If A[i] is not present in the hash table then skip it.
3. Return.

उदाहरण

हम कहते हैं

A[]={3, 3, 1, 2 ,1}

बाईं ओर की तालिका हमारे इनपुट सरणी और वर्तमान सूचकांक के लिए बैंगनी रंग बिंदु है।

दाईं ओर की तालिका है हैश टेबल

किसी सरणी में गैर-दोहराए जाने वाले तत्वों (अलग) तत्वों का योग खोजें

किसी सरणी में गैर-दोहराए जाने वाले तत्वों (अलग) तत्वों का योग खोजें

कोड

C ++ कोड

#include <bits/stdc++.h>
using namespace std;
void sumOfDistinctElements(vector<int> A)
{
    int n = A.size();
    int sum = 0;
    unordered_set<int> hash_table;
    for (int i = 0; i < n; i++)
    {
        if (hash_table.count(A[i]) == 0) //hash_table.count(x) returns 1 if x is present in the hash_table otherwise returns 0
        {
            hash_table.insert(A[i]);
            sum += A[i];
        }
    }
    cout << "Sum of distinct Elements in the array is: " << sum << endl;
    return;
}
int main()
{
    vector<int> A = {1, 4, 2, 1, 5, 2, 3, 2};
    sumOfDistinctElements(A);
    return 0;
}
Sum of distinct Elements in the array is: 15

जावा कोड

import java.util.*;
public class Main
{   
    static void sumOfDistinctElements(int A[])
    {
        int n = A.length;
        int sum = 0;
        HashSet<Integer> hash_table = new HashSet<Integer>(); 
        for (int i = 0; i < n; i++) 
        { 
            if (!hash_table.contains(A[i])) 
            { 
                sum += A[i]; 
                hash_table.add(A[i]); 
            } 
        } 
        System.out.println("Sum of distinct Elements in the array is: " + sum);
        return;
    }
  public static void main(String[] args) {
    int A[] = {1, 4, 2, 1, 5, 2, 3, 2};
        sumOfDistinctElements(A);
  }
}
Sum of distinct Elements in the array is: 15

जटिलता विश्लेषण

समय की जटिलता

हम सरणी को केवल एक बार पुनरावृत्त करते हैं और अनियंत्रित सेट में डालने के कार्य की समय जटिलता हे (1) है, इसलिए कुल समय जटिलता है पर)।

अंतरिक्ष की जटिलता

हमने एक अतिरिक्त हैश तालिका ली ताकि हमारी अंतरिक्ष जटिलता हो पर)।