கொடுக்கப்பட்ட தொகையுடன் ஜோடியை எண்ணுங்கள்


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அகோலைட் அமேசான் உண்மை உயர்வு
அணி ஹேஷிங் கணித வரிசையாக்க

சிக்கலில் “கொடுக்கப்பட்ட தொகையுடன் ஜோடி எண்ணுங்கள்” நாங்கள் ஒரு முழு எண்ணைக் கொடுத்துள்ளோம் வரிசை[] மற்றும் மற்றொரு எண் 'தொகை' என்று கூறுகிறது, கொடுக்கப்பட்ட வரிசையில் உள்ள இரண்டு உறுப்புகளில் ஏதேனும் ஒன்று "கூட்டுத்தொகைக்கு" சமமானதா என்பதை நீங்கள் தீர்மானிக்க வேண்டும்.

உதாரணமாக

உள்ளீடு:

arr [] = {1,3,4,6,7} மற்றும் தொகை = 9.

வெளியீடு:

"கொடுக்கப்பட்ட உறுப்புகள் காணப்படுகின்றன தொகை ”சமமாக '3' மற்றும் '6' இருப்பதால் '9' க்கு.

உள்ளீடு:

arr [] = {11,3,5,7,10} மற்றும் தொகை = 20.

வெளியீடு:

'8' க்கு சமமான தொகை கொண்ட எந்த எண்ணும் இல்லாததால் "கொடுக்கப்பட்ட தொகையுடன் கூறுகள் காணப்படவில்லை".

அல்காரிதம்

  1. ஒரு அறிவிக்கவும் தொகுப்பு.
  2. 0 முதல் 'i' வரை வரிசையின் நீளத்தை விட குறைவாக இருக்கும்.
    1. J ஐ sum-arr [i] என அமைக்கவும்.
    2. தொகுப்பில் 'j' உள்ளதா என சரிபார்க்கவும், உண்மை என்றால் j மற்றும் arr [i] ஐ அச்சிடுங்கள், இது ஜோடியாக இருக்கும்.
    3. மற்றொன்று தொகுப்பில் arr [i] ஐச் சேர்க்கவும்.

விளக்கம்

நாங்கள் ஒரு சிக்கல் அறிக்கையை வழங்கியுள்ளோம், அதில் எங்களுக்கு முழு எண் வரிசையுடன் வழங்கப்படுகிறது மற்றும் ஒரு எண் 'தொகை' என்று கூறுகிறது. கொடுக்கப்பட்ட “தொகைக்கு” ​​சமமான ஒரு கூட்டுத்தொகையைக் கொண்ட இரண்டு கூறுகளில் ஏதேனும் ஒரு வரிசையில் உள்ளதா என்பதை தீர்மானிப்பதே எங்கள் பணி.

எங்கள் முக்கிய யோசனை ஹாஷ்செட்டைப் பயன்படுத்துவதும் ஒரு ஜோடியைக் கண்டுபிடிப்பதும் ஆகும். அதற்காக நாம் பயணிக்கும் போது கூட்டுத்தொகையின் வித்தியாசத்தையும் வரிசையின் ஒவ்வொரு மதிப்பையும் சேமிக்கப் போகிறோம், ஏனென்றால் ஒரு ஜோடிக்கு அந்த இரண்டு கூறுகளும் உள்ளன, மேலும் ஒரு குறிப்பிட்ட தொகை மற்றொரு உறுப்பைக் கண்டுபிடிப்பதற்கான திறவுகோலாகும், அதனால்தான் அனைத்து வரிசை கூறுகளையும் தொகுப்பில் சேமிக்கிறோம் ஜோடிகளில் உள்ள உறுப்புகளில் ஒன்று இருக்கிறதா இல்லையா என்பதைப் பாருங்கள்.

அதைக் கண்டுபிடிக்க, நாங்கள் ஒரு ஹாஷிங் முறையைப் பயன்படுத்துவோம்.

ஒரு உதாரணத்தை எடுத்துக் கொள்வோம்:

arr [] = {1, 4, 45, 6, 10, 8};

  • i = 0, மைசெட், தொகை = 16;

j = sum-arr [i];

அது j = 16-1 = 15 மற்றும் நிச்சயமாக 'j' ஒரு வரைபடத்தில் இருக்காது.

எனவே இது மைசெட்டில் '1' என்று அர் [i] ஐ சேர்க்கிறது.

  • i = 1, மைசெட் = {1}, தொகை = 16;

j = sum-arr [i];

அது j = 16-4 = 12 மற்றும் நிச்சயமாக 'j' ஒரு வரைபடத்தில் இல்லை.

எனவே இது மைசெட்டில் '4' என்று அர் [i] ஐ சேர்க்கிறது.

  • i = 2, மைசெட் = {1, 4}, தொகை = 16;

j = sum-arr [i];

அது j = 16-45 = -29 மற்றும் நிச்சயமாக 'j' ஒரு வரைபடத்தில் இருக்காது.

எனவே இது மைசெட்டில் '45' என்று அர் [i] ஐ சேர்க்கிறது.

  • i = 3, மைசெட் = {1, 4, 45}, தொகை = 16;

j = sum-arr [i];

அதாவது j = 16-6 = 10 மற்றும் j ஒரு வரைபடத்தில் இல்லை.

எனவே இது மைசெட்டில் '6' என்று அர் [i] ஐ சேர்க்கிறது.

  • i = 4, மைசெட் = {1, 4, 45, 6}, தொகை = 16;

j = sum-arr [i];

அதாவது j = 16-10 = 6 மற்றும் j வரைபடத்தில் உள்ளது.

ஜோடியின் மற்றொரு உறுப்பைக் கண்டுபிடிப்பது இங்குதான். நாங்கள் ஏற்கனவே 16 மற்றும் 10 ஆகிய தேதிகளில் செயல்பட்டுள்ளோம்.

நாங்கள் அச்சிடுகிறோம்:

“கொடுக்கப்பட்ட தொகையை 16 எனக் கண்டறிந்த கூறுகள் (10, 6);

அதாவது "தொகை" க்கு சமமான தொகையைக் கொண்ட இரண்டு கூறுகள் வரிசையில் உள்ளன.

நடைமுறைப்படுத்தல்

கொடுக்கப்பட்ட தொகையுடன் கவுண்ட் ஜோடிக்கான சி ++ நிரல்

#include <bits/stdc++.h>
using namespace std;

void getPairOfSum(int arr[], int arr_size, int sum)
{
    unordered_set<int> myset;
    for (int i = 0; i < arr_size; i++)
    {
        int j = sum - arr[i];
        if (myset.find(j) != myset.end())
        {
            cout << "Found elements with the given sum as "<<sum << " is (" << arr[i] <<", " << j << ")"<<endl;
        }
        myset.insert(arr[i]);
    }
}
int main()
{
    int arr[] = { 1, 4, 45, 6, 10, 8 };
    int sum = 16;
    int arr_size = sizeof(arr) / sizeof(arr[0]);
    getPairOfSum(arr, arr_size, sum);
    return 0;
}
Found elements with the given sum as 16 is (10, 6)

கொடுக்கப்பட்ட தொகையுடன் கவுண்ட் ஜோடிக்கான ஜாவா நிரல்

import java.io.*;
import java.util.HashSet;

class twoElementSum {
  public static void getPairOfSum(int arr[], int sum) {
    HashSet<Integer> myset = new HashSet<Integer> ();
    for (int i = 0; i<arr.length; ++i) {
      int j = sum - arr[i];
      if (myset.contains(j)) {
        System.out.println("Found elements with the given sum as " + sum + " is (" + arr[i] + ", " + j + ")");
      }
      myset.add(arr[i]);
    }
  }
  public static void main(String[] args) {
    int arr[] = { 1, 4, 45, 6, 10, 8 };
    int sum = 16;
    getPairOfSum(arr, sum);
  }
}
Found elements with the given sum as 16 is (10, 6)

கொடுக்கப்பட்ட தொகையுடன் எண்ணிக்கை ஜோடிக்கான சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (n) முழு வரிசையும் ஒரு முறை மட்டுமே பயணிக்க வேண்டும் என்பதால்.

விண்வெளி சிக்கலானது

ஓ (n) வரிசை கூறுகளை சேமிக்க ஹாஷ் வரைபடம் பயன்படுத்தப்பட்டுள்ளது.

குறிப்பு