Question

Write a program to find pairs of positive integers (a, b) whose sum is equal to the input number n (n < 10 power 6). The conditions to be satisfied by a & b are: a has at least two digits and starts with a non-zero digit b always has one digit less than a b can start with 0 b is obtained from a by leaving out one digit. The output should also indicate the number of such pairs. For example, if we input 1002 to the program, the output should be as follows:

Answer 1

Answer:

Explanation:

METHOD 1 (Use Sorting)

Algorithm :

hasArrayTwoCandidates (A[], ar_size, sum)

1) Sort the array in non-decreasing order.

2) Initialize two index variables to find the candidate  

  elements in the sorted array.

      (a) Initialize first to the leftmost index: l = 0

      (b) Initialize second  the rightmost index:  r = ar_size-1

3) Loop while l < r.

      (a) If (A[l] + A[r] == sum)  then return 1

      (b) Else if( A[l] + A[r] <  sum )  then l++

      (c) Else r--    

4) No candidates in whole array - return 0

Time Complexity: Depends on what sorting algorithm we use. If we use Merge Sort or Heap Sort then (-)(nlogn) in worst case. If we use Quick Sort then O(n^2) in worst case.

Auxiliary Space : Again, depends on sorting algorithm. For example auxiliary space is O(n) for merge sort and O(1) for Heap Sort.