Monthly Archives: March 2013
Project Euler Problem# 5 solution in C++
/**
Project Euler problem# 5:
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
Below is an efficient solution of above problem using C++. Time complexity in the random access machine model is O(n log log n)
operations, a direct consequence of the fact that the prime harmonic series asymptotically approaches log log n.
*/
#include <iostream>
using namespace std;
//Finding Prime Numbers using the sieve of Eratosthenes, one of a number of prime number sieves,
//is a simple, ancient algorithm for finding all prime numbers up to any given limit.
// it is not an trial and check algorithm but find prime numbers by jumping out.
//The sieve of Eratosthenes is one of the most efficient ways to find all of the smaller primes (below 10 million or so)
int find_prime (int *numArray, int maxNum)
{
int factor = 2; // we will make 2 as the starting point.
numArray[1] = 0; // rule out 1 from our logic to avoid incorrect results.
// loop condition will check, if we are in our maximum number limit.
//maxNum is the number till there we can find the prime numbers.
while ((factor * factor) < maxNum)
{
for (int i = 2; i < maxNum; i++) // we start our itration from number 2 not from 0 or 1 to get correct results.
{
if (numArray[i] != 0) //if a number on current array index is not zero, it is a prime or we haven’t yet checked it.
{
// we are putting zeros on all multiples of prime numbers, one by one.
if (numArray[i] != factor && (numArray[i]% factor) == 0)
{
numArray[i] = 0;
}
}
}
++factor;
}// after the loop, array will have zeros on all non prime locations and prime numbers.
}
int main ()
{
int maxNum = 0;
int result = 1;
int num = 0;
cout << “enter max number: “;
cin >> maxNum;
int *myArray = new int [maxNum];
//we fill up the array till the number we want to find the smallest positive number that is evenly divisible.
for (int i = 0; i < maxNum; i++)
{
myArray[i]= i;
}
// we will get prime numbers till the maxNum by calling below function.
find_prime(myArray, maxNum);
// returning array will have prime numbers and zeros on non prime locations.
// we start our loop from 2 as first two locations are not use full so we reduce the itration of the loop.
for (int i = 2; i < maxNum; i ++)
{
// we only do our calculation on prime numbers.
if ((myArray [i]) != 0)
{
num = myArray[i];
// we take multiples of each prime number till the maxNum. meaning we raise each prime to power of a number.
// which result will remain till maxNum.
while ((num * (myArray[i])) < maxNum)
{
num = num * (myArray[i]);
}
result = num * result;
}
}// after the loop result will have smallest positive number that is evenly divisible by all of the numbers from 1 to maxNum.
cout << “smallest positive number that is evenly divisible by all of the numbers from 1 to ” << maxNum
<< ” is: ” << result <<endl;
delete []myArray;
}
Related articles
- Project Euler: Problem # 3 solution in C++ (alikhuram.wordpress.com)
- Largest prime number found! (quantumfrontiers.com)
- US professor finds longest prime number with 17,425,170 digits (ndtv.com)
- Prime numbers (haskell.org)
Smart Array (Linked List template implementation using C++)
As we have discussed about the Smart Array (Linked List) in our previous post and showed the Node class as well as the header file for the linked list. Below is the actual implementation of Linked List template in C++.
Any questions welcomed!
#include “list.h”
template <class T>
// in constructor we add a head node in the class as well as the cursor which we called current node.
// head node and current node set to null as there are no other nodes to point to.
List<T>::List()
{
headNode = new Node<T>();
headNode->setNext(NULL);
headNode->setLast(NULL);
currentNode = NULL;
size = 0;
}
//in destructor we do memory management as we did made nodes dynamically.
template <class T>
List<T>::~List ()
{
while (size != 0)
{
remove_node();
}
delete currentNode;
delete headNode;
}
// this function simply call remove_node function until all nodes are deleted.
template <class T>
bool List<T>::clear_list ()
{
while (size != 0)
{
remove_node ();
}
delete currentNode;
}
// this is the main addition of a node function.
template <class T>
void List<T>::add (T addObject)
{
Node<T> *newNode = new Node<T>();
newNode->set(addObject);
size ++;
if(currentNode != NULL) // in case we already have other nodes in the list
{
lastNode = currentNode;
newNode->setNext(currentNode->getNext()); // pointer will be adjusted for the new node.
if (newNode->getNext()!= NULL) // if the node is not at the end of the list.
{
currentNode = currentNode->getNext();
currentNode->setLast(newNode);
}
newNode->setLast(lastNode);
currentNode = newNode;
lastNode->setNext(newNode);
newNode->setIndex(size);
}
else // if this the very first node to be added in the list. this else part will be executed once in the life span of list.
{
newNode->setNext(NULL);
headNode->setNext(newNode);
newNode->setLast(headNode);
currentNode = newNode;
newNode->setIndex(size);
}
}
// this function return the current node value.
template <class T>
T List<T>::get()
{
if (currentNode != NULL)
{
return currentNode->get();
}if (currentNode == headNode) // if cursor is pointing towards head node. we cannot return anything as head node doesn’t
// have any value.
{
return false;
}
}
// move the cursor to next node only if the cursor is not reached on the last node.
template <class T>
bool List<T>::move_next()
{
if (currentNode->getNext() == NULL) return false ;
currentNode = currentNode->getNext();
}
//move the cursor to backwards only if the cursor is not reached till head node.
template <class T>
bool List<T>::move_back ()
{
if (currentNode->getLast() == headNode) return false;
currentNode = currentNode->getLast();
}
//move the cursor to very first node after head node, if there are any nodes in the list.
template <class T>
bool List<T>::move_first()
{
if (headNode->getNext()!=NULL)
currentNode = headNode->getNext();
}
//move the cursor to last node.
template <class T>
bool List<T>::move_last()
{
while (currentNode->getNext() != NULL)
{
currentNode= currentNode->getNext();
}
return currentNode;
}
//delete current node where cursor pointing to.
template <class T>
bool List<T>::remove_node()
{
Node<T> *temp = currentNode;
if (currentNode != NULL) // if cursor is actually pointing to a valid node
{
if (currentNode->getLast() == headNode) // if cursor is on the very first node after head node.
{
currentNode = headNode;
currentNode->setNext(NULL);
currentNode->setLast(NULL);
delete temp;
size–;
return true;
}else if (currentNode->getNext() == NULL) //if cursor is pointing to the very last node of the list.
{
move_back();
currentNode->setNext(NULL);
delete temp;
size–;
return true;
}else // if the cursor is not at the start or end of the list but somewhere in the middle.
{
move_back();
currentNode->setNext(temp->getNext());
move_next();
currentNode->setLast(temp->getLast());
delete temp;
size–;
return true;
}
}
}
//move the cursor to next node.
template <class T>
Node<T> List<T>::operator++()
{
move_next();
return *currentNode;
}
//move theh cursor to last node.
template <class T>
Node<T> List<T>::operator–()
{
move_back();
return *currentNode;
}
// add one node and assign rvalue to it. the name of list instance is used as lvalue.
template <class T>
Node<T> List<T>::operator=(T i)
{
add(i);
}
//cout object can be used to display list values.
template <class T>
std::ostream& operator << (std::ostream& leftOpr, List<T>& rhs)
{
leftOpr << rhs.get();
return leftOpr;
}
//cin can be used to add one node and assign it a value directing getting input from user.
template <class T>
std::istream& operator >> (std::istream& leftOpr, List<T>& rhs)
{
int i = 0;
leftOpr >> i;
rhs.add(i);
return leftOpr;
}
//return size of the list. number of nodes in the list.
template <class T>
int List<T>::get_size()
{
return size;
}
//return node value by index.
template <class T>
Node<T> List<T>::return_node(int i)
{
move_first();
while (currentNode->getNext() != NULL)
{
if (currentNode->getIndex() == i)
return *currentNode;
else
move_next();
}
}
//brackets can be used to access list elements by giving index as used in simple array.
template <class T>
Node<T> List<T>::operator[](int i)
{
return_node(i);
}
Related articles
- Data Structures implemantation in C++ (alikhuram.wordpress.com)
- Intersecting Linked Lists Faster (twistedoakstudios.com)
- doublelinkedBag (daniweb.com)
Project Euler Problem #2 Solution in Java
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
/**
* @author Khuram Ali
*/
public class Problem2
{
public static void main(String[] args)
{
int term_1 = 1;
int term_2 = 2;
int term_3 = 0;
int sum = 0;
long MaxTerm = 4000000;
while (term_1 <= MaxTerm)
{
System.out.println (term_1);
if ((term_1 %2) == 0){sum += term_1;}
term_3 = term_1 + term_2;
term_1 = term_2;
term_2 = term_3;
}
System.out.println (“the sum of even value numbers is: “);
System.out.println (sum);
}
}
Related articles
- Project Euler: Problem #2 solution in C++ (alikhuram.wordpress.com)
- Project Euler Problem #1 Solution in Java (alikhuram.wordpress.com)
- C++, Fibonacci Sequence, Largest Value (daniweb.com)
- Project Euler: Problem #1 solution in C++ (alikhuram.wordpress.com)
- Project Euler Problem #4 C++ solution: (alikhuram.wordpress.com)
- Project Euler: Problem # 3 solution in C++ (alikhuram.wordpress.com)
Project Euler Problem #1 Solution in Java
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
Solution in Java:
package problem1;
/**
* @author Khuram Ali
*/
public class Problem1
{
public static void main(String[] args)
{
int maxNum = 1000;
int result = 0;
for (int i = 2; i < maxNum; i++)
{
if (i % 5 == 0)
{
result += i;
}else if (i % 3 == 0)
{
result += i;
}
}
System.out.println (“total of multiples of 3 or 5: “) ;
System.out.println (result);
}
}
Data Structures implemantation in C++
I have implemented data structures in C++ with some tweaks. These are custom made for some specific needs which I have. These might be interesting for anyone who is interested in data structures and learn how to implement them. There can be many methods which I can think of and can provide with these data structures but as I have said earlier, I wrote these for some specific needs. However, if someone is interested to know or want some added functionality, I can help!
Any questions are welcomed!
/* The Node class
A node is basic building block of many user define data structures.
Below node class is used to implement double linked list, stack and Queue data structures.
As this node class will become a part of a larger data structures, it doesn’t contain utility functions and operators.
this is a smart node, which also keeps track index of itself. as well as the address of last node
and the next node.
the class is implemented as template so can be instantiated with any data type.
Author: Khuram Ali
*/
template <class T>
class Node
{
public:
Node<T> (){object;} //a node constructor can be called with a value which needs to be stored.
T get() { return object; }; //getter function for out putting value stored in a node.
void set(T object) { this->object = object; }; //setting value of a node.
Node<T> *getNext() { return nextNode; }; // return a pointer to next node.
Node<T> *getLast(){return lastNode;}; // return a pointer to last node.
void setNext(Node<T> *nextNode) { this->nextNode = nextNode; }; // set a pointer to next node.
void setLast (Node<T> *lastNode) {this->lastNode = lastNode;};//set a pointer to last node.
void setIndex (int num) {this->index = num;}; // set index of node.
int getIndex () {return index;}; // return the index of node.
private:
T object;
int index = 0;
Node<T> *nextNode;
Node<T> *lastNode;
};
ifndef LIST_H_INCLUDED
#define LIST_H_INCLUDED
/* Smart Array header file:
this is a linked list implementation and I called it a smart array as you can do all, what you used to do with arrays,
with the flexibility of linked list. it is a double linked list so you can move forward and back easily. you can use
arithmetic operators as well as [] to access any node by its index. you can use iostream objects to print the elements on
the screen as you can do with normal array. though you can access any index of the list but if the list is big enough there is
a give n take on efficiency with ease of use. accessing a list element through index in a very large array is less efficient, if
the speed is what you want.
it is a template class so you can create a list of any data type.
Author Khuram Ali
*/
#include <iostream>
#include “node.cpp”
template <class T>
class List
{
public:
List();
~List();
void add (T); // function used to add an element (node) in the list.
T get(); //return current node value.
int get_size(); // return size of the list (number of nodes in a list)
bool move_next(); // move to next node and can go forward.
bool move_back (); // move to last node and can go backward.
bool move_first (); // move the cursor to first node.
bool move_last (); // move the cursor to last node.
bool remove_node (); // delete current node.
bool clear_list (); // delete all nodes in the list.
Node<T> return_node (int); // return node value by index.
Node<T> operator ++(); // move the cursor to next node.
Node<T> operator –(); // move the cursor to last node.
Node operator = (T); // add a new node and assign the rvalue to it.
Node<T> operator [] (int); // return node value by index.
template <class W>
friend std::ostream& operator << (std::ostream&, List<W>&); // printing node value on screen using cout.
template <class S>
friend std::istream& operator >> (std::istream&, List<S>&); // getting value from user from cin and add a new node
// with that value.
private:
int size;
Node<T> *headNode;
Node<T> *currentNode;
Node<T> *lastNode;
};
#endif // LIST_H_INCLUDED
/** implementation of List data structure will be added shortly.
Related articles
- Top 15 Data Structures and Algorithm Interview Questions for Java programmer – Answers (javarevisited.blogspot.com)
- Data Warehouse Dilemma | Solving Real Problems | Domo | Blog (domo.com)
- basic applications of data structure (stackoverflow.com)
- Help with implementing a linked list as an array in JAVA (daniweb.com)
- Why do we need pointers/references? (mortoray.com)
Project Euler Problem #4 C++ solution:
/** (From:http://projecteuler.net/index.php?section=problems&id=3)
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 
99.
Find the largest palindrome made from the product of two 3-digit numbers.
Solution: (Brute force)
#include <iostream>
#include <string>
#include <sstream>
using namespace std;
void check(int);
int main ()
{
int result = 0;
for (int i = 999; i >= 101; i–)
{
for (int j = i; j >= 101; j–)
{
result = (j *i);
check (result);
}
}
}
void check (int a)
{
string str = static_cast<std::ostringstream*>( &(std::ostringstream() << a) )->str();
string syl_1;
string syl_2;
string syl_3;
static string j ;
int len = (str.length()/2);
syl_1 = str.substr(0, len);
syl_2 = str.substr(len);
for (int i = syl_2.length(); i >=0; i –)
{
if (syl_2[i] != NULL)
syl_3 += syl_2[i];
}
if ((syl_1.compare(syl_3))==0)
{
if (j < str)
j = str;
if (str == j)
cout << j << endl;
}
}
Project Euler: Problem # 3 solution in C++
/** (From:http://projecteuler.net/index.php?section=problems&id=3)
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ? */
#include <iostream>
using namespace std;
int main ()
{
long long factorOf = (600851475143);
int num = 2;
while ((num * num) <= factorOf)
if (factorOf % num == 0)
{
cout << num << endl;
factorOf /= num;
}else
num++;
cout << “factor of 600851475143 is: ” << factorOf << endl;
}
Project Euler: Problem #2 solution in C++
/**(From:http://projecteuler.net/index.php?section=problems&id=2)
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
Solution:*/
#include <iostream>
using namespace std;
int main()
{
int term_1 = 1;
int term_2 = 2;
int term_3 = 0;
int MaxTerm = 0;
int sum = 0;
cout<< “This Program lists the Fibonacci sequence. Please enter the Max number you want to have sequence:” << endl;
cin >> MaxTerm ;
while (term_1 <= MaxTerm)
{
cout<< term_1 << endl;
if ((term_1 %2) == 0){sum += term_1;}
term_3 = term_1 + term_2;
term_1 = term_2;
term_2 = term_3;
}
cout << “the sum of even value numbers is: “<< sum << endl;
}
Project Euler: Problem #1 solution in C++
/**(From:http://projecteuler.net/index.php?section=problems&id=1)
Problem Description:
If we list all the natural numbers below 10 that are multiples of 3 or 5,
we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
Solution:*/
#include <iostream>
using namespace std;
int main ()
{
int maxNum = 0;
int result = 0;
cout << “Please enter max number limit for the sum of all the multiples of 3 or 5: “;
cin >> maxNum;
for (int i = 2; i < maxNum; i++)
{
if (i % 5 == 0)
{
result += i;
}else if (i % 3 == 0)
{
result += i;
}
}
cout << “total of multiples of 3 or 5: ” << result << endl;
}
Date Class implementation
this is a follow up post of Date class header file code and have the actual implementation of Date class in C++:
#include “Date.h”
// initializing the no of days, take 0 for month zero.
const short Date::daysInMonth[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
// creating and initializing arrey for giving a alfabatical output.
const char *mArray [] = {“*”,”Jan”, “Feb”, “Mar”, “Apr”, “May”, “Jun”, “Jul”, “Aug”, “Sep”, “Oct”, “Nov”, “Dec”};
Date::Date(short d, short m , short y)
{
setDate(d,m,y);
}
void Date::display()
{
std::cout << “\nDate: ” << day << “-” << mArray[month] << “-” << year;
}
void Date::setDate (short d, short m, short y)
{
year = y;
//if month is wrong then set it to 1
if (month < 1 && month > 12)
month = 1;
else
month = m;
//if day is wrong then set it to 1
if (month == 2 && leapYear(y))
if (d >= 1 && d <=29)
day = d;
else
day = 1;
else
if (d >=1 && d <= daysInMonth[month])
day = d;
else
day = 1;
}
short Date::daysOfMonth(Date d)
{
if (d.month == 2 && leapYear(d.year)) //if leap year then Feb is 29 days.
return 29;
else
return daysInMonth [d.month];
}
bool Date::leapYear(short y)
{
if ((y%400 == 0)|| (y%100 !=0 && y%4 ==0))
return true;
else
return false;
}
Date Date::operator-(short numberOfDays)
{
for (short i = 1; i <= numberOfDays; i++)
{
–(*this);
}
return *this;
}
Date operator -(short num, Date rhs)
{
for (short i =1; i <= num ; i++)
{
–rhs;
}
return rhs;
}
short Date::operator – (Date a)
{
short numDays =0;
Date rhs, lhr;
if ((*this) > a)
{
rhs = (*this);
lhr = a;
}
else
{
rhs = a;
lhr = (*this);
}
while (lhr != rhs)
{
–rhs;
numDays++;
}
return numDays;
}
Date Date::operator+(short numberOfDays)
{
for (short i =1; i <= numberOfDays; i++)
{
++(*this);
}
return *this;
}
Date Date::operator++()
{
if (day== daysOfMonth(*this) && month == 12) //end of year
{
day = 1;
month = 1;
++year;
}
else if (day == daysOfMonth(*this)) //last day of month
{
day = 1;
++month;
}
else //not the last day of the month
{
day++;
}
return *this;
}
Date Date::operator–()
{
if (day == 1 && month == 1) //start of year
{
day = 31;
month = 12;
–year;
}
else if (day == 1) //first day of month
{
–month;
day = daysOfMonth(*this);
}
else // not the first day of month
{
day–;
}
return *this;
}
Date Date::operator+=(short a)
{
for (short i =0; i <=a; i ++)
{
++(*this);
}
return *this;
}
Date Date::operator -= (short a)
{
(*this)-a;
return *this;
}
short Date::operator -=(Date rhs)
{
short numDays= 0;
numDays = (*this) – rhs;
return numDays;
}
bool Date::operator <(Date rhs)
{
if (year < rhs.year)
{
return true;
}
else if (month < rhs.month)
{
return true;
if (day < rhs.day)
{
return true;
}else
return false;
}
else
{
return false;
}
}
bool Date::operator >(Date rhs)
{
if (year > rhs.year)
{
return true;
}
else if (month > rhs.month)
{
return true;
if (day > rhs.day)
{
return true;
}else
return false;
}
else
{
return false;
}
}
bool Date::operator <=(Date rhs)
{
if (year <= rhs.year)
{
return true;
}
else if (month <= rhs.month)
{
return true;
if (day <= rhs.day)
{
return true;
}else
return false;
}
else
{
return false;
}
}
bool Date::operator >=(Date rhs)
{
if (year >= rhs.year)
{
return true;
}
else if (month >= rhs.month)
{
return true;
if (day >= rhs.day)
{
return true;
}else
return false;
}
else
{
return false;
}
}
bool Date::operator ==(Date rhs)
{
if (year == rhs.year && month == rhs.month && day == rhs.day)
{
return true;
}
else
{
return false;
}
}
bool Date::operator !=(Date rhs)
{
if (year == rhs.year && month == rhs.month && day == rhs.day)
{
return false ;
}
else
{
return true;
}
}
std::ostream& operator << (std::ostream& leftOpr, Date & rhs)
{
leftOpr << rhs.day << “-” << mArray[rhs.month] << “-” << rhs.year;
return leftOpr;
}
std::istream& operator >> (std::istream& leftOpr, Date & rhs)
{
{
leftOpr >> rhs.day ;
leftOpr.ignore();
leftOpr >> rhs.month;
leftOpr.ignore();
leftOpr >> rhs.year;
}
return leftOpr;
}
Khuram Ali 