Answer to Question #283338 in C++ for kalpana T

Question

You are set out travel for your "Magical Vacation" and you are given a choice to take two destinations. You draw up multiple destination starting at asingle origin with different routes. Suppose different routes from torigin are represented complete binary tree height h, with number of node, n = 2 ^h - 1, where each node and each leaf of this tree ha associated cost "c" (any arbitrary real number). The destination are leaves of the tree. You can compute the cost to destination (leaf node) by summing up avalues of the nodes on the path up root, including leaf node itself. You are to find two destination has the lowest cost as your choice for vacation ie., x,y (two leaves). you can find cost by summing up all nodes in the path up the root. nodes only once [ie., you are taking the union of the ancestors up to origin]. Write a program to compute the lowest destination pair – that is of all leaf combinations which pair gives the lowest cost. Example: C(x,y) = 9 + 15+12 + 14+19+54 =123

Answer 1

#include <bits/stdc++.h>

using namespace std;



// Returns number of pairs in arr[0..n-1] with sum equal

// to 'sum'

int getPairsCount(int arr[], int n, int sum) {

    int count = 0; // Initialize result



    // Consider all possible pairs and check their sums

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

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

            if (arr[i] + arr[j] == sum)

                count++;



    return count;

}



// Driver function to test the above function

int main() {

    int arr[] = { 1, 5, 7, -1, 5 };

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

    int sum = 6;

    cout << "Count of pairs is "

         << getPairsCount(arr, n, sum);

    return 0;

}