Algorithm for summation of doubles

Question

Given a vector V of integers, ordered, and a value s, write a complexity algorithm O(n) to compute how many pairs of numbers have sum s. In this vector there may be repeated numbers. Note that if V contains p occurrences of the number x and q occurrences of y and if x+y = s, the total of pairs relative to x and y with sum s is p*q.

I was able to do it for when there are no repeat numbers, but I can’t adapt...

v=[2,5,8,20,24,30] #vetor de exemplo. S=50. Nesse caso a única dupla é (20,30)

c=0
i=1
j=1
while i < j:
   se V[i] + V[j] < s:
         i=i+1
   senão se V[I] + v[J] > S;
         j = j+1
   senão:
         c = c+1
         i=i+1
         j=j+1
escrever(d) 

Answer 1

Hello, I made the code in language c, the vector V is static, but the value of S is an input value. The program takes the pairs that the sum is equal to S. The code is commented on in key lines. Any doubt just ask.

int v[] = {2,5,8,20,24,30};
int s, controle=0; 
int par1[TAM], par2[TAM]; // Vetores onde vão ser guardados os valores que se somados são igual a S
printf("Valor de S: ");
scanf("%d",&s);
for(int i = 0; i < sizeof(v)/sizeof(int); i++){ // Laço de repetição que vai de 0 ao tamanho do vetor V
    for(int j = 0; j < sizeof(v)/sizeof(int); j++){
        if(v[i] + v[j] == s){ // Se o valor da soma for igual a S a atribuição é feita logo a baixo
            par1[controle] = v[i];
            par2[controle] = v[j];
            controle++;
        }
    }
}
for(int i = 0; i < controle; i++){ 
    printf("Pares: %d %d \n", par1[i], par2[i]); // Printa os pares na tela 
}
}

Answer 2

I made an example of code in python, first thing I thought was to do using 2 for however we know that the level of complexity of this would be O(n 2). So starting from this principle we could use binary search, that is, we would go through each item of the array and for each item we would do a binary search to see if there are any pairs for that item. However even using binary search for this it would not be with the complexity of O(n), and for this there is this other algorithm in which I do not remember the name where you go through the array once, and for each item you would store its complement.

Linear search

The linear search will perform 2 for and add each item if the item is equal to the sum it will add the list. Example in python:

def busca_linear(vetor, valor):
  '''Busca linear, essa busca ira percorrer cada
  elemento do array e verificar se os pares podem
  se juntar, porem isso faz com que tenhamos que
  percorrer o array 2 vezes fazendo com que o nível
  de complexidade seja de О(n^2).
  '''
  pares = list()

  for i in vetor:
    for j in vetor:
      if i + j == valor:
        pares.append((i, j))

  print('[BUSCA_LINEAR] Pares achados: {}'.format(pares))

Binary search

In short what binary search does and use the idea of divide and conquer, that is, it will take the middle of the vector and verify if the number to be found is the middle number, otherwise it checks whether the number would be greater or less than the middle number, If it’s smaller he continues to search for the smaller side if it’s bigger he looks for the bigger side. If you want to study more about binary search see the wiki at en or pt. Python example:

def busca_binaria(vetor, low, high, valor):
  '''Busca pelo elemento valor e retorna seu index

    param vetor: Lista
    param low: Menor index
    param high: Maior index
    param valor: O valor a ser buscado

    Retorna o index do valor caso tenha sido encontrado,
    caso contrario ele retorna -1
  '''

  while low <= high:

    mid = low + (high - low) / 2

    if vetor[mid] == valor:
      return mid
    elif vetor[mid] < valor:
      low = mid + 1
    else:
      high = mid - 1

  return -1


def achar_pares_binaria(vetor, valor):
  '''Ira percorrer uma vez o vetor, porem para cada item do vetor
  ele ira realizar uma busca binaria para achar seu par, buscas
  binarias podem ser O(n) no melhor caso e O(log n) no pior caso.
  '''

  pares = list()

  for i in vetor:
    # Busca o index do valor que completaria o par do mesmo
    par = busca_binaria(vetor, 0, len(vetor) - 1, valor - i)

    if par > 0:
      pares.append((i, vetor[par]))

  print('[ACHAR_PARES_BINARIA] Pares achados: {}'.format(pares))

Solucao O(n)

It traverses each item of the vector and stores what its pair would be to complete the sum. For each vector item it will store its complement for example if the sum is 10 and the vector [1, 2, 9, 24, 30]the first item of the vector would be 1 its complement would be 9 so it stores the value 9. When it arrives at the value of nine in the array it will check if that value is in the complement list, if yes it will add the pair list. Python example:

def achar_pares(vetor, valor):
  '''Percorre cada item do vetor e armazena qual seria seu par
    para completar a soma.
  '''

  pares = list()
  complementos = list()

  for i in vetor:
    if i in complementos:
      pares.append((i, valor - i))

    complementos.append(valor - i)

  print('[ACHAR_PARES] Pares achados: {}'.format(pares))

All functions and their times

In this code below I put all the functions described above, the code was made in python and the same will calculate the execution time of each function and at the end will print in order of execution.

# -*- coding: utf-8 -*-
import time

def busca_linear(vetor, valor):
  '''Busca linear, essa busca ira percorrer cada
  elemento do array e verificar se os pares podem
  se juntar, porem isso faz com que tenhamos que
  percorrer o array 2 vezes fazendo com que o nivel
  de complexidade seja de О(n^2).
  '''
  pares = list()

  for i in vetor:
    for j in vetor:
      if i + j == valor:
        pares.append((i, j))

  print('[BUSCA_LINEAR] Pares achados: {}'.format(pares))


def busca_binaria(vetor, low, high, valor):
  '''Busca pelo elemento valor e retorna seu index

    param vetor: Lista
    param low: Menor index
    param high: Maior index
    param valor: O valor a ser buscado

    Retorna o index do valor caso tenha sido encontrado,
    caso contrario ele retorna -1
  '''

  while low <= high:

    mid = low + (high - low) / 2

    if vetor[mid] == valor:
      return mid
    elif vetor[mid] < valor:
      low = mid + 1
    else:
      high = mid - 1

  return -1


def achar_pares_binaria(vetor, valor):
  '''Ira percorrer uma vez o vetor, porem para cada item do vetor
  ele ira realizar uma busca binaria para achar seu par, buscas
  binarias podem ser O(n) no melhor caso e O(log n) no pior caso.
  '''

  pares = list()

  for i in vetor:
    # Busca o index do valor que completaria o par do mesmo
    par = busca_binaria(vetor, 0, len(vetor) - 1, valor - i)

    if par > 0:
      pares.append((i, vetor[par]))

  print('[ACHAR_PARES_BINARIA] Pares achados: {}'.format(pares))


def achar_pares(vetor, valor):
  '''Percorre cada item do vetor e armazena qual seria seu par
    para completar a soma.
  '''

  pares = list()
  complementos = list()

  for i in vetor:
    if i in complementos:
      pares.append((i, valor - i))

    complementos.append(valor - i)

  print('[ACHAR_PARES] Pares achados: {}'.format(pares))


def main():
  vetor = [1, 2, 5, 8, 9, 9, 20, 24, 30]
  valor = input('Valor a ser buscado dentro do array ({}): '.format(vetor))

  times = list()
  start = time.time()
  busca_linear(vetor, valor)
  times.append(time.time() - start)

  start = time.time()
  achar_pares_binaria(vetor, valor)
  times.append(time.time() - start)

  start = time.time()
  achar_pares(vetor, valor)
  times.append(time.time() - start)

  for t in range(len(times)):
    print("Tempo [{}] de: {}".format(t, times[t]))

if __name__ == '__main__':
  main()

Exit:

Valor a ser buscado dentro do array ([1, 2, 5, 8, 9, 9, 20, 24, 30]): 10
[BUSCA_LINEAR] Pares achados: [(1, 9), (1, 9), (2, 8), (5, 5), (8, 2), (9, 1), (9, 1)]
[ACHAR_PARES_BINARIA] Pares achados: [(1, 9), (2, 8), (5, 5), (8, 2)]
[ACHAR_PARES] Pares achados: [(8, 2), (9, 1), (9, 1)]
Tempo [0] de: 0.000350952148438
Tempo [1] de: 0.000414133071899
Tempo [2] de: 0.000170946121216