Find pairs Algorithm

Question

I'm trying to write a function in CPP to find how many pairs in array.

I got Segmentation Fault on this case --> [10, 20, 20, 10, 10, 30, 50, 10, 20]

The Algorithm I'm trying to use is find out how many time the Number repeated and divided by 2.

Input --> [10, 20, 20, 10, 10, 30, 50, 10, 20]

out put --> 3

Explanation :

There is 4 of items[10] --> 4/2 = 2.

there is 3 items[20] --> 3/2 = 1 Note get rid of any fraction

Here is my code :-

int sockMerchant(int n, vector<int> ar) {
int pairs = 0;
int arRange = 0;

for(int i = 0; i < n; i++)
{
    if(ar[i] > ar[arRange])
    arRange = ar[i];    
}

arRange += 1;
int freq[arRange] = {0};
for(int i = 0; i < n; i++)
    freq[ar[i]]++;


for(int i = 0; i <= arRange; i++)
{
    int count = 0;
    if(freq[i] > 1)
    count = freq[i] / 2;
    
    pairs = pairs + count;    
}

return pairs;

}

your description is not clear. What "pairs" are you looking for? What do you mean with "how many time the Number repeated and divided by 2." ? What is the expected output? — 463035818_is_not_an_ai, Apr 25 '22 at 09:06
`int freq[arRange] = {0};` is not standard C++. [Why aren't variable-length arrays part of the C++ standard?](https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard) — 463035818_is_not_an_ai, Apr 25 '22 at 09:07
your freq array has arRange entries, but your loop goes to 0 to arRange included. this is one spotted issue. why do you need to include it, just use < and not <= — user2147873, Apr 25 '22 at 09:07
@463035818_is_not_a_number pairs of numbers like [10] and there is another [10] This means 1 pair and so on . — khalid Morrshid, Apr 25 '22 at 09:23
k identical elements define binomial(k,2) pairs, or k-1 if you want them sort of consecutive, not k/2, that's why people are asking you to clarify. Here apparently you have a sock drawer and are trying to extract pairs, where one sock can only be in one pair. — Marc Glisse, Apr 25 '22 at 09:40

score 0 · Answer 1 · answered Apr 25 '22 at 09:32

This code will Segmentation Fault when the number n is bigger than ar.size().

It will also segfualt depeding on arRange. to repeat @user2147873 comment. "your freq array has arRange entries, but your loop goes to 0 to arRange included" So you will always acces 1 element outside of the freq array.

A third way this will segfault is by just giving it some bignumbers. for example vector<int> ar{1000000000, 1000000000}; This will segfualt on line 6. were you try to index they 1000000000 element of your ar.

Find pairs Algorithm

1 Answers1