Power of 2 or not ?

How to find a number is power of 2 or not ?

bool IsPowerOfTwo(unsigned long x)
{
    return (x != 0) && (x & (x - 1)) == 0);
}

Explanation:

The above function returns bool (true/false) and accepts one incoming parameter of type unsigned long (x, in this case). Lets take an example, that someone has passed value 4 to the function like:

bool b = IsPowerOfTwo(4);

Now replace each occurance of x with 4:

return (4 != 0) && ((4 & (4-1)) == 0); 


We already know (4 != 0) , so the evaluation of the expression is true.


((4 & (4-1)) == 0)  translates to:


((4 & (3)) == 0) 


But what exactly is  4&3 ? The binary representation of 4 is 100 and of 3 is 011. The & operation says that if both values are equal to 1, then the result is 1. Otherwise it is 0.

100
011
----
000

The result is simply 0. So we go back and look at what our return statement now translates to:

return (4 != 0) && ((4 & 3) == 0);

Which translates now to:

return true && (0 == 0);

return true && true;

We all know that true && true is simply true, and this shows that for our example, 4 is a power of 2.

const

What is the difference between char const * and char * const ?

According to the standard, const modifies the element directly to its left. The use of
 const  at the beginning of a declaration is just a convenient mental shortcut. So the following two statements are equivalent:

char const * pointerToConstantContent;
const char * pointerToConstantContent;

In order to ensure the pointer itself is not modifiable,  const  should be placed after the asterisk:

char * const constantPointerToMutableContent;

To protect both the pointer and the content to which it points, we should use two consts as below:

char const * const constantPointerToConstantContent;

Search in a Circular Sorted Array

Given a circular sorted array say A = { 2,3,4,5,6,7,8,9,0,1 }, find a number in it.

If the array is not circular, we can use binary search to find the key. But if the array is circular we don't know where is the starting point (pivot element). Obviously we can do a linear search to find the element. But if the input array is very large the worst case performance will be very bad. We can take advantage of the fact that the array is sort and use binary search algorithm to find the element in O(N log N).

Approach:

Find the middle value of the input array a.

If a[0] < a[mid], then all values in the first half of the array are sorted.

If a[mid] < a[last], then all values in the second half of the array are sorted.

Take the sorted half, and check whether your value lies within it (key lies between the sorted half).

• If so, binary search that half.
• If it doesn't, it must be in the unsorted half. Take that half and repeat this process

 
#include <iostream>
#include <vector>
#include <assert.h>

template<typename T, typename type>
int binary_search(const T& a, int left, 
                  int right, type key) {

    while (left <= right) {
        int mid = (right-left)/2 + left;

        // base case 1
        if (a[mid] == key)
            return mid;

        // mid less than key. Move to right
        if (a[mid] < key) {
            left = mid+1;
        }
        else {
            right = mid-1;
        }
    }

    return -1;
}

template<typename T, typename type>
int circular_search(const T& a, int left, 
                    int right, type key) {

    // base case 1
    int mid = (right-left)/2 + left;
    if (a[mid] == key)
        return mid;

    // left array is sorted.
    if (a[0] < a[mid]) {

        if (key > a[left] && key < a[mid]) {
            return binary_search(a, left, mid-1, key);
        }
        else {
            return circular_search(a, mid+1, right, key);
        }
    }
    // right array is sorted
    else if (a[mid] < a[right]) {
        if (key > a[mid] && key < a[right])
            return binary_search(a, mid+1, right, key);
        else
            return circular_search(a, left, mid-1, key);

    }

    return -1;

}

template<typename T>
void print(const T&a) {
    typedef typename T::const_iterator iterator;
    iterator start = a.begin();
    iterator end = a.end();
    for(; start!=end; ++start)
        std::cout << *start << " ";
    std::cout << std::endl;
}

int main() {
    typedef std::vector<int> Input;
    Input temp;
    int n =0;
    
    // get n from user
    std::cin >> n;

    for(int i=0; i<n; ++i) {
        temp.push_back(i*2);
    }
    Input data;
    data.resize(temp.size());

    // Rotate the input sequence
    std::rotate_copy(temp.begin(), temp.begin()+4, 
                     data1.end(), data.begin());
    print(data);

    // get key from user
    int key=0;
    std::cin >> key;

    int found = circular_search<Input, int>(data, 0, n-1, key);
    if (found)
    {
        assert(key == data[found]);
        std::cout << data[found] 
                  << " found @ pos " 
                  << found << std::endl;
    }
    else
        std::cout << key 
                  << " not found" 
                  << std::endl;

    return 0;

}

Hamming sequence

Hamming's Problem

Hamming wants an efficient algorithm that generates the list, in ascending order, of all numbers of the form 2ⁱ3^j5^k for i,j,k at least 0. This list is called the Hamming sequence. The list begins like this:
1 2 3 4 5 6 8 9 10 12 15 16 18 ...

Brute force technique:

Take the first number you haven't checked yet, divide it by 2's, 3's and 5's until you can't do that any more, and if you're left with 1, then the number should go on the list; otherwise throw it away and try the next number. So:

• Is 19 on the list? No, because it's not divisible by 2, 3, or 5.
• Is 20 on the list? Yes, because after we divide it by 2, 2, and 5, we're left with 1.
• Is 21 on the list? No, because after we divide it by 3, we're left with 7, which isn't divisible by 2, 3, or 5.

This obvious technique has one problem: it's unbelievably slow. The problem is that most numbers aren't on the list, and you waste an immense amount of time discovering that. Although the numbers at the beginning of the list are pretty close together, the 2,999th number in the list is 278,628,139,008. Even if you had enough time to wait for the brute-force algorithm to check all the numbers up to 278,628,139,008, think how much longer you'd have to wait for it to finally find the 3,000 number in the sequence, which is 278,942,752,080.

Linear Solution:

The idea is that to calculate a[i], we can use a[j]*2 for some j < i. But we also need to make sure that:
1) a[j]*2 > a[i - 1] and
2) j is smallest possible.

Then, a[i] = min(a[j]*2, a[k]*3, a[t]*5)

 
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main(void) {
  // get n from user
  unsigned n;
  cout <<"n: ";
  cin >>n;

  // list of ugly numbers
  vector <uint64_t> ugly;
  uint64_t x = 1;
  ugly.push_back(x);

  // index of next multiple
  unsigned i2 = 0, i3 = 0, i5 = 0;

  // value of next multiple
  uint64_t x2 = 2, x3 = 3, x5 = 5;

  // loop through ugly numbers
  for(unsigned a = 1; a < n; a++) {

    x = std::min(x2, std::min(x3,x5));

    ugly.push_back(x);
    if (x == x2) { i2++; x2 = ugly[i2] * 2; }
    if (x == x3) { i3++; x3 = ugly[i3] * 3; }
    if (x == x5) { i5++; x5 = ugly[i5] * 5; }
  }

  // return last ugly number found
  cout << x << endl;
  return 0;

}

HowEasy - Topcoder Arena

Problem Statement :
  
***Note: Please keep programs under 7000 characters in length. Thank you

Class Name: HowEasy
Method Name: pointVal
Parameters: String
Returns: int

TopCoder has decided to automate the process of assigning problem difficulty
levels to problems. TopCoder developers have concluded that problem difficulty
is related only to the Average Word Length of Words in the problem statement:

If the Average Word Length is less than or equal to 3, the problem is a 250
point problem.
If the Average Word Length is equal to 4 or 5, the problem is a 500 point
problem.
If the Average Word Length is greater than or equal to 6, the problem is a 1000
point problem.

Definitions:
Token - a set of characters bound on either side by spaces, the beginning of
the input String parameter or the end of the input String parameter.
Word - a Token that contains only letters (a-z or A-Z) and may end with a
single period. A Word must have at least one letter.
Word Length - the number of letters in a Word. (NOTE: a period is NOT a letter)

The following are Words :
"ab", "ab."

The following are not Words :
"ab..", "a.b", ".ab", "a.b.", "a2b.", "."

Average Word Length - the sum of the Word Lengths of every Word in the problem
statement divided by the number of Words in the problem statement. The
division is integer division. If the number of Words is 0, the Average Word
Length is 0.

Implement a class HowEasy, which contains a method pointVal. The method takes
a String as a parameter that is the problem statement and returns an int that
is the point value of the problem (250, 500, or 1000). The problem statement
should be processed from left to right.

Here is the method signature (be sure your method is public):
int pointVal(String problemStatement);

problemStatement is a String containing between 1 and 50 letters, numbers,
spaces, or periods. TopCoder will ensure the input is valid.

Examples:

If problemStatement="This is a problem statement", the Average Word Length is
23/5=4, so the method should return 500.
If problemStatement="523hi.", there are no Words, so the Average Word Length is
0, and the method should return 250.
If problemStatement="Implement a class H5 which contains some method." the
Average Word Length is 38/7=5 and the method should return 500.
If problemStatement=" no9 . wor7ds he8re. hj.." the Average Word Length is 0,
and the method should return 250.
Definition
  
Class: HowEasy
Method: pointVal
Parameters: string
Returns: int
Method signature: int pointVal(string param0)
(be sure your method is public)
 

 
#include <iostream>
#include <sstream>
#include <string>

const static 
std::string g_LegalCharacters =  "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

class HowEasy
{
    public:
        int pointVal(std::string problemStmt);

    private:
        inline bool isValid(std::string &token);
        inline int problemValue (unsigned int length);
};

bool HowEasy::isValid(std::string &token)
{
    if (token.empty()) return 0;

    size_t pos = token.find_first_not_of(g_LegalCharacters);
    return (pos == std::string::npos);
}

int HowEasy::pointVal(std::string problemStmt)
{
    std::istringstream iss;
    iss.str( problemStmt );

    std::string token;
    unsigned int nWords = 0;
    unsigned int lWords = 0;
    unsigned int average = 0;
    int points = 0;
    std::string validString;
    while (!iss.eof())
    {
        iss >> token;
        if (token.length())
        {
            if (token[token.length() - 1] == '.')
                token.erase(token.end() - 1);

            if (isValid(token))
            {
                ++nWords;
                lWords += token.length();
                validString += token;
            }
        }
    }
    
    if (lWords && nWords)
        average = lWords / nWords;
        
    points =  problemValue (average);        
    return points;    
}

int HowEasy::problemValue (unsigned int length)
{
    if (length <= 3)
        return 250;
    else if (length <= 5)
        return 500;
    else
        return 1000;
}

Compare Vector V1 and V2 for equality

Here are the ways to compare two vectors.

Method 1:

 
#include < iostream >
using std::cout;
using std::endl;

#include < algorithm >
#include < vector >
#include < iterator >

int main()
{
   int a1[ 10 ] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
   int a2[ 10 ] = { 1, 2, 3, 4, 9, 6, 7, 8, 9, 10 };
   std::vector<> v1( a1, a1 + 10 );
   std::vector<> v2( a1, a1 + 10 );
   std::vector<> v3( a2, a2 + 10 );
   std::ostream_iterator<> output( cout, " " );

   cout << "Vector v1 contains: ";    
   std::copy( v1.begin(), v1.end(), output );    
   cout << "\nVector v2 contains: ";
   std::copy( v2.begin(), v2.end(), output );
   cout << "\nVector v3 contains: ";
   std::copy( v3.begin(), v3.end(), output );

   // compare vectors v1 and v2 for equality    
   bool result = std::equal( v1.begin(), v1.end(), v2.begin() );    
   cout << "\n\nVector v1 " 
        << ( result ? "is" : "is not" )
        << " equal to vector v2.\n"
        return 0;
}

Method 2:

Overload the == operator for comparision

 

inline bool operator == (const std::vector< std::string >, 
                         const std::vector< std::string >)
{
    if (lhs.size() != rhs.size())
        return false;

    int count = lhs.size();
    std::vector< std::string >::const_iterator lhsi = lhs.begin();
    std::vector< std::string >::const_iterator rhsi = rhs.begin();
    while (count--)
    {
        if ( *lhsi != *rhsi)
            return false;
        lhsi++; rhsi++;
    }
    return true;
}

Convert "man page" into text file

Save a man page into text file

Option #1

man -P cat ls > man_ls.txt

Option #2:

man ls | col -b > ls.txt

First try in C#

Here is my first try in C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace dotNet
{
    class Greeting
    {
        public static int displayGanesh()
        {
            Console.WriteLine("Ganesh Here !!");
            return 0;
        }
        public static int displayVishnu()
        {
            Console.WriteLine("Vishnu Here !!");
            return 1;
        }
    }

    delegate int delGreetings();

    class Program
    {
        static void Main(string[] args)
        {
            int choice = 1;
            delGreetings[] Greetings =
            {
              new delGreetings(Greeting.displayGanesh),
              new delGreetings(Greeting.displayVishnu)
            };
            int return_ = Greetings[choice - 1]();
            Console.Write("Return Value ");
            Console.WriteLine(return_);
            return;
        }
    }
}

delegate is basically defines the function pointer.
In the below snippet, it defines a function pointer which
takes no arguments and returns an int value.

delegate int delGreetings();

Happy Hacking !!