tHe puZZlingG wOrlD: July 2011

Saturday, July 30, 2011

When do we pass arguments by reference or pointer?

In C++, variables are passed by reference due to following reasons:

1) To modify local variables of the caller function: A reference (or pointer) allows called function to modify a local variable of the caller function. For example, consider the following example program where fun() is able to modify local variable x of main().

void fun(int &x) {
    x = 20;
}
 
int main() {
    int x = 10;
    fun(x);
    cout<<"New value of x is "<< code="">
    return 0;
}

Output:
New value of x is 20

2) For passing large sized arguments: If an argument is large, passing by reference (or pointer) is more efficient because only an address is really passed, not the entire object. For example, let us consider the following Employee class and a function printEmpDetails() that prints Employee details.

class Employee {
private:
    string name;
    string desig;
 
    // More attributes and operations
};
 
void printEmpDetails(Employee emp) {
     cout<
     cout<
 
    // Print more attributes
}

The problem with above code is: every time printEmpDetails() is called, a new Employee abject is constructed that involves creating a copy of all data members. So a better implementation would be to pass Employee as a reference.

void printEmpDetails(const Employee &emp) {
     cout<
     cout<
 
    // Print more attributes
}

This point is valid only for struct and class variables as we don’t get any efficiency advantage for basic types like int, char.. etc.

3) To avoid Object Slicing: If we pass an object of subclass to a function that expects an object of superclass then the passed object is sliced if it is pass by value. For example, consider the following program, it prints “This is Pet Class”.

#include 
#include
 
using namespace std;
 
class Pet {
public:
    virtual string getDescription() const {
        return "This is Pet class";
    }
};
 
class Dog : public Pet {
public:
    virtual string getDescription() const {
        return "This is Dog class";
    }
};
 
void describe(Pet p) { // Slices the derived class object
    cout<
}
 
int main() {
    Dog d;
    describe(d);
    return 0;
}

Output:
This is Pet Class

If we use pass by reference in the above program then it correctly prints “This is Dog Class”. See the following modified program.

#include 
#include
 
using namespace std;
 
class Pet {
public:
    virtual string getDescription() const {
        return "This is Pet class";
    }
};
 
class Dog : public Pet {
public:
    virtual string getDescription() const {
        return "This is Dog class";
    }
};
 
void describe(const Pet &p) { // Doesn't slice the derived class object.
    cout<
}
 
int main() {
    Dog d;
    describe(d);
    return 0;
}

Output:
This is Dog Class

This point is also not valid for basic data types like int, char, .. etc.

As a side note, it is a recommended practice to make reference arguments const if they are being passed by reference only due to reason no. 2 or 3 mentioned above. This is recommended to avoid unexpected modifications to the objects.

Thursday, July 28, 2011

Find the minimum distance between two numbers

Source

Given an unsorted array arr[] and two numbers x and y, find the minimum distance between x and y in arr[]. The array might also contain duplicates. You may assume that both x and y are different and present in arr[].

Examples:
Input: arr[] = {1, 2}, x = 1, y = 2
Output: Minimum distance between 1 and 2 is 1.

Input: arr[] = {3, 4, 5}, x = 3, y = 5
Output: Minimum distance between 3 and 5 is 2.

Input: arr[] = {3, 5, 4, 2, 6, 5, 6, 6, 5, 4, 8, 3}, x = 3, y = 6
Output: Minimum distance between 3 and 6 is 4.

Input: arr[] = {2, 5, 3, 5, 4, 4, 2, 3}, x = 3, y = 2
Output: Minimum distance between 3 and 2 is 1.

1) Traverse array from left side and stop if either x or y are found. Store index of this first occurrrence in a variable say prev
2) Now traverse arr[] after the index prev. If the element at current index i matches with either x or y then check if it is different from arr[prev]. If it is different then update the minimum distance if needed. If it is same then update prev i.e., make prev = i.

Thanks to wgpshashank for suggesting this approach.

#include 
#include   // For INT_MAX
 
int minDist(int arr[], int n, int x, int y)
{
   int i = 0;
   int min_dist = INT_MAX;
   int prev;
 
   // Find the first occurence of any of the two numbers (x or y)
   // and store the index of this occurence in prev
   for (i = 0; i < n; i++)
   {
     if (arr[i] == x || arr[i] == y)
     {
       prev = i;
       break;
     }
   }
 
   // Traverse after the first occurence
   for ( ; i < n; i++)
   {
      if (arr[i] == x || arr[i] == y)
      {
          // If the current element matches with any of the two then
          // check if current element and prev element are different
          // Also check if this value is smaller than minimm distance so far
          if ( arr[prev] != arr[i] && (i - prev) < min_dist )
          {
             min_dist = i - prev;
             prev = i;
          }
          else
             prev = i;
      }
   }
 
   return min_dist;
}
 
/* Driver program to test above fnction */
int main()
{
    int arr[] ={3, 5, 4, 2, 6, 3, 0, 0, 5, 4, 8, 3};
    int n = sizeof(arr)/sizeof(arr[0]);
    int x = 3;
    int y = 6;
 
    printf("Minimum distance between %d and %d is %d\n", x, y,
              minDist(arr, n, x, y));
    return 0;
}

Output: Minimum distance between 3 and 6 is 4

Time Complexity: O(n)

Please write comments if you find the above codes/algorithms incorrect, or find other ways to solve the same problem.