Question

Array processing (elimination of three largest values) (one of many array reduction problems) The array a(1..n) contains arbitrary integers. Write a function reduce(a,n) that reduces the array a(1..n) by eliminating from it all values that are equal to three largest different integers. For example, if a=(9,1,1,6,7,1,2,3,3,5,6,6,6,6,7,9) then three largest different integers are 6,7,9 and after reduction the reduced array will be a=(1,1,1,2,3,3,5), n=7. The solution should have the time complexity O(n).

Answer 1

Explanation:

#include <iostream>

#include <algorithm>

using namespace std;

void reduce(int a[], int& n) {

// find the three largest unique integers

int largest[3] = {a[0], a[0], a[0]}; // initialize with first element

int count = 1; // count the number of unique integers

for (int i = 1; i < n; i++) {

if (a[i] > largest[0]) {

largest[2] = largest[1];

largest[1] = largest[0];

largest[0] = a[i];

if (count < 3) count++;

}

else if (a[i] > largest[1] && a[i] < largest[0]) {

largest[2] = largest[1];

largest[1] = a[i];

if (count < 3) count++;

}

else if (a[i] > largest[2] && a[i] < largest[1]) {

largest[2] = a[i];

if (count < 3) count++;

}

}

// remove all values equal to the three largest unique integers

int j = 0; // index for non-removed elements

for (int i = 0; i < n; i++) {

if (a[i] != largest[0] && a[i] != largest[1] && a[i] != largest[2]) {

a[j] = a[i];

j++;

}

}

n = j; // update array size

}

int main() {

int a[] = {9,1,1,6,7,1,2,3,3,5,6,6,6,6,7,9};

int n = sizeof(a) / sizeof(a[0]);

reduce(a, n);

for (int i = 0; i < n; i++) {

cout << a[i] << " ";

}

cout << endl << "n = " << n << endl;

return 0;

}

Answer 2

Explanation:

# include <bits/stdc++.h>

using namespace std;

bool find3Numbers(int A[], int arr_size, int sum)

{

int l, r;

sort(A, A+arr_size);

for (int i=0; i<arr_size-2; i++)

{

l = i + 1;

r = arr_size-1;

while (l < r)

{

if( A[i] + A[l] + A[r] == sum)

{

printf("Triplet is %d, %d, %d", A[i],

A[l], A[r]);

return true;

}

else if (A[i] + A[l] + A[r] < sum)

l++;

else // A[i] + A[l] + A[r] > sum

r--;

}

}

return false;

}

int main()

{

int A[] = {1, 4, 3, 2, 10, 8};

int sum = 22;

int arr_size = sizeof(A)/sizeof(A[0]);

find3Numbers(A, arr_size, sum);

return 0;

}