#include <iostream>
using namespace std;
inline void swap(int arr[],int i,int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
int randint(int len) {
srand(time(NULL));
//srand((unsigned)rdtsc());
return (rand() % (len) + 0);
}
int randomPartition(int arr[],int start , int end) {
int pivotPos = randint(end-start) + start;
swap(arr,start,pivotPos);
int pivot = arr[start], i = start+1, j= start+1;
pivotPos = start;
for(;j<=end; j++) {
if(arr[j] < pivot) {
swap(arr,i,j);
i++;
}
}
swap(arr,pivotPos,i-1);
pivotPos = i-1;
return pivotPos;
}
int Rselect(int arr[],int start, int end, int k) {
int pivotPos = randomPartition(arr,start,end);
if(pivotPos == k)
return arr[k];
else if(pivotPos < k)
return Rselect(arr,pivotPos+1,end,k);
else
return Rselect(arr,start,pivotPos-1,k);
}
int main() {
int arr[] = {40,1,10,70,2,5,30,9,8,6};
int size = sizeof arr/sizeof arr[0];
cout<<"Kth greatest = "<<Rselect(arr,0,size-1,3);
system("pause");
return 0;
}
Monday 14 October 2013
Quick select: Select Kth smallest element in an array of size n in O(n) time.
Knuth-Morris-Pratt Pattern Matching Algorithm
//============================================================================
// Name : KMP.cpp
// Author : Varun Sharma
// Complexity : O(P) pre-processing O(T) kmpMatching, O(P+T).
// Copyright :
// Description : Knuth-Morris-Pratt pattern matching Algo.
//============================================================================
/*
PRE-PROCESSING
==============
Construct an array kmp[] that stores the no. of positions by which one should move the pattern in case of mismatch at character i.
Kmp[i] = Length of longest prefix in pattern[0…i] which is also suffix of pattern[0…i].
Pattern : AABAAC
Pattern[0..4] = AABAA.
Longest prefix and suffix in Patern[0…4] = AA hence Kmp[4] = 2
String A A B A A C
KMP 0 1 0 1 2 0
1. Create an array kmp[] and set kmp[0] = 0 and set len =0.
2. For i=1 to patternLength.
len will keep track of prefix, while i will scan entire string from left to right.
3. Check if char at i matches char at len, pattern[i] == pattern[len]
a. If match occurs increment len (len++) and set kmp[i] = len and increment I (i++).
b. If no match, then
i. If len = 0, i.e. at beginning of pattern, then set kmp[i] = 0 and increment i
ii. Else shift pattern by kmp[len-1], do not increment I and repeat step 3.
KMP MATCHING
============
1. Preprocessing : Build the preprocessing Array.
2. Use t for scanning Text and p for scanning pattern, t=p=0.
3. If text[t] == patter[p] then increment p and t (p++, t++)
a. If p == pattern length, then pattern occurs in string and print.
4. Else There is a mismatch.
a. If p==0 i.e. at first character in pattern, then increment t and start matching from first character in pattern.
b. Else use pre-processing array to determine matching position (p)
set p = kmp[p-1].
*/
#include <iostream>
using namespace std;
void preprocessing(int *kmp, string pattern, int pLen) {
kmp[0] = 0;
int len,i;
for(i=1,len=0; i<pLen; ) {
//Check if char at i matches char at len.
if(pattern[i] == pattern[len]) {
//If match occurs increment len and set kmp[i] = len.
len++;
kmp[i] = len;
i++;
}
else {
//If characters don't match and len = 0, i.e. at very first character.
//Then set kmp[i] = 0 and simply increment i.
if(!len) { kmp[i] = 0; i++;}
else
//else repeat matching step by shifting pattern by kmp[len-1].
len = kmp[len-1];
}
}
}
void kmpMatching(string text , string pattern) {
int tLen, pLen , t, p;
tLen = text.length();
pLen = pattern.length();
//if length of text is greater than length of pattern then return.
if(tLen < pLen) {
cout<<"Pattern Doesn't exist";
return;
}
//Build kmp array as part of preprocessing step.
int *kmp = new int[pLen];
preprocessing(kmp,pattern,pattern.length());
//p is use to traverse in pattern.
//t is use to traverse in text.
for(t = p =0; t<tLen; ) {
//If character at p in pattern
//and character at t in text
//match then increment p and t.
if(text[t] == pattern[p]) {
t++; p++;
//if p = pattern length then pattern occurs.
if(p==pLen) {
cout<<"n Pattern Occurs at : "<<t-pLen+1<<" position";
p = 0;
}
}else {
//if p = 0, i.e. very first character in pattern.
//Then increment text and start matching from pattern[p].
if(!p) t++;
//else if p!=-0 then set p = kmp[p-1] and start matchng from pattern[p].
else p = kmp[p-1];
}
}
}
int main() {
string text = "I google about google.";
string pattern = "google";
kmpMatching(text,pattern);
return 0;
}
Sunday 6 October 2013
Implementation of Bellman Ford Algorithm.
/*
ALGORITHM (Borrowed from wiki)
==============================
procedure BellmanFord(list vertices, list edges, vertex source)
// This implementation takes in a graph, represented as lists of vertices and edges,
// and fills two arrays (distance and predecessor) with shortest-path information
// Step 1: initialize graph
for each vertex v in vertices:
if v is source then distance[v] := 0
else distance[v] := infinity
predecessor[v] := null
// Step 2: relax edges repeatedly
for i from 1 to size(vertices)-1:
for each edge (u, v) with weight w in edges:
if distance[u] + w < distance[v]:
distance[v] := distance[u] + w
predecessor[v] := u
// Step 3: check for negative-weight cycles
for each edge (u, v) with weight w in edges:
if distance[u] + w < distance[v]:
error "Graph contains a negative-weight cycle"
BELLMAN FORD VS DIJKSTRA
========================
1. Bellman Ford runs in O(VE) time where as Dijkstra can be optimized to run in O(VlogV) time with use of Fibonacci heap.
2. Bellman ford works on negative weight graphs as well where as Dijkstra doesn’t allow negative weight edges.
3. Dijkstra algorithm is highly centric and is not very distributive. Dijkstra is good if all data is stored on one machine’s main memory.
COMPLEXITY
==========
O(VE)
*/
public void bellmanFord(int sourceVertex) {
int i,j,cost;
Vertex source,target;
boolean negativeCycle = false;
int distance[] = new int[totalVertices];
// Step 1: initialize graph
//Set distance of each vertex from source to INF and distance source = 0
for(i=0; i<totalVertices; i++)
distance[i] = INF;
distance[sourceVertex] = 0;
// Step 2: relax edges repeatedly
//Relax each edge by 1,2...|V|-1
//Complexity : O(|V|).
//Longest cycle free path between 2 vertices can have atmost |v|-1 edges.
for(i=0; i<totalVertices-1; i++) {
//Explore each edge. Complexity : O(|E|)
for(j=0; j<totalVertices; j++) {
source = vertices[j];
for(Edge e : source.edges) {
target = e.Target;
cost = distance[source.vertexId] + e.weight;
//If current distance is greater than new reachable distance.
//then update distance.
if(distance[target.vertexId] > cost) {
distance[target.vertexId] = cost;
}
}
}
}
// Step 3: check for negative-weight cycles
//Detect negative weight cycles by relaxing to |V| edges.
//If there is a negative cycle in the path then simply report it.
for(j=0; j<totalVertices; j++) {
source = vertices[j];
for(Edge e : source.edges) {
target = e.Target;
cost = distance[source.vertexId] + e.weight;
if(distance[target.vertexId] > cost) {
negativeCycle = true;
System.out.println("NEGATIVE WEIGHT CYCLE IN GRAPH");
break;
}
}
}
}
Implementation of Dijkstra, single source shortest path.
/*
ALGORITHM
=========
1. Initialize distance of each vertex from source as INF, and distance back to source = 0.
2. For I = 0 to Total vertices Repeat step 3 to 4.
3. Find minimum distance vertex, which is not yet explored and put it to explored set.
4. Find all vertices reachable from current vertex and update its distance if it is less than distance[currentVertex] + edge weight.
COMPLEXITY
==========
Time : O(|V||E|) .
Time complexity can be improved by using Fibonacci heap to retrieve minimum value.
Time : O(|E| + |V|log|V|).
LIMITATIONS
===========
• Dijkstra algorithm can be used for graphs with all positive weight edges only.
• Dijkstra is not lacks distribute property.
*/
public int minimum(int distance[],boolean visited[]) {
int min = INF,minNode = -1;
int i;
for(i=0; i<totalVertices; i++) {
if(distance[i] <= min && visited[i] == false) {
min = distance[i];
minNode = i;
}
}
return minNode;
}
public void dijkstra(int sourceVertex) {
System.out.println("nnDIJKSTRA");
int i,j,minV,cost;
Vertex minVertex,target;
//Distance array to store distance of each vertex from sourcevertex
int distance[] = new int[totalVertices];
boolean visited[] = new boolean[totalVertices];
//Initialize distance array with INF, and distance[source] = 0.
for(i=0; i<totalVertices; i++) {
visited[i] = false;
distance[i] = INF;
}
distance[sourceVertex] = 0;
for(i=0; i<totalVertices; i++) {
//Get minimum vertex out of all unexplored vertex
//and put it to explored set.
minV = minimum(distance,visited);
visited[minV] = true;
if(distance[minV] == INF)
continue;
minVertex = vertices[minV];
//compute the distance, if it is less than current distance then update it.
for(j=0; j<minVertex.edges.size(); j++) {
cost = distance[minV] + minVertex.edges.get(j).weight;
target = minVertex.edges.get(j).Target;
if(cost < distance[target.vertexId]) {
distance[target.vertexId] = cost;
}
}
}
}
Topological Sort.
/*
PRE-CONDITION
=============
Graph should be Acyclic and Directed (DAG).
APPLICATIONS
============
• Ordering of formula cell evaluation when recomputing formula values in spreadsheets,
• Logic synthesis.
• Determining the order of compilation tasks to perform in makefiles.
• Data serialization
• Resolving symbol dependencies in linkers.
• It is also used to decide in which order to load tables with foreign keys in databases.
ALGORITHM
=========
1. Put all the vertices in unexplored set.
2. While unexplored set is not empty, Repeat step 3 to 5
3. Select a vertex from unexplored set and perform DFS taking this as source,
4. Remove vertex in DFS path from unexplored set and put them in explored set.
5. Print the last node in DFS exploration (sink node).
*/
public void printSinkNodeDFS(Vertex source, boolean visited[]) {
//Move the vertex to explored set.
visited[source.vertexId] = true;
for(int i=0; i<source.edges.size(); i++) {
//Get all the vertices reachable from current vertex and present in unexplored set.
Vertex target = source.edges.get(i).Target;
if(!visited[target.vertexId])
printSinkNodeDFS(target, visited);
}
//When there are no more unexplored vertices reachable from current node.
//Process the current node which is now the sink node.
System.out.print(" " + source.vertexId);
}
public void topologicalSort() {
System.out.println("nnTopological Sort");
int i;
//Initially each vertex is in unexplored set.
boolean visited[] = new boolean[totalVertices];
for(i=0; i<totalVertices; i++)
visited[i] = false;
//Scan all vertices in unexplored set and perform DFS with first unscanned vertex as source.
//Move vertices from unexplored to explored set.
//Repeat until no vertex is present in unexplored set.
for(i=0; i<totalVertices; i++) {
if(!visited[i]) {
printSinkNodeDFS(vertices[i],visited);
}
}
}
Friday 4 October 2013
Depth First Search
/*
TIME COMPLEXITY :
O(|v| + |E|).
APPLICATIONS OF DFS
Finding strongly connected components in a graph (Kosaraju Algorithm).
Topological Sorting.
Solving Maze.
*/
public void recursiveDFS(Vertex sourceVertex,boolean visited[]) {
//Process the top vertex from stack and put it to explored set of vertices.
visited[sourceVertex.vertexId] = true;
System.out.println(sourceVertex.vertexId);
for(int i=0; i<sourceVertex.edges.size(); i++) {
//Push all not visited vertices reachable from process vertex
//one by one and aggressively search to deeper levels.
//backtrack when no more path can be taken and
//process all other vertices reachable from processed vertex
Vertex target = sourceVertex.edges.get(i).Target;
if(!visited[target.vertexId]) {
recursiveDFS(target,visited);
}
}
}
public void DFS(int sourceVertex) {
System.out.println("DFS Traversal");
int i;
//Initially put all vertices in unexplored set.
boolean visited[] = new boolean[totalVertices];
for(i=0; i<totalVertices; i++)
visited[i] = false;
//Push source vertex in stack.
recursiveDFS(vertices[sourceVertex],visited);
}
Breadth First Search in a Graph.
/*
ALGORITHM
Enqueue the root node
Dequeue a node and examine it
If the element sought is found in this node, quit the search and return a result.
Otherwise enqueue any successors (the direct child nodes) that have not yet been discovered.
If the queue is empty, every node on the graph has been examined – quit the search and return "not found".
If the queue is not empty, repeat from Step 2.
COMPLEXITY
BFS is very first and runs in linear time O(|V| + |E|) since each vertex and edge is explored once in worst case.
APPLICATIONS
Finding shortest path between 2 nodes in an undirected graph.
Checking if a graph is bipartite
Ford Fulkerson method for computing maximum flow in a network.
Serialization/Deserialization of a binary tree.
Finding all nodes within one connected components.
*/
public void BFS(int sourceVertex) {
System.out.println("BFS Traversal");
int i,targetId;
ArrayList<Vertex> queue = new ArrayList<>();
boolean visited[] = new boolean[totalVertices];
//Put all the vertices to unexplored set of vertices, initially.
for(i=0; i<totalVertices; i++)
visited[i] = false;
//Put source vertex to explored vertices set.
visited[sourceVertex] = true;
queue.add(vertices[sourceVertex]);
while(!queue.isEmpty()) {
//Remove the very first vertex from the queue.
Vertex vertex = queue.get(0);
queue.remove(0);
//Process the removed vertex.
System.out.println(vertex.vertexId);
for(i=0; i<vertex.edges.size(); i++) {
//Get all the vertices reachable from processed vertex and add them to queue.
//put the processed vertex to explored set of vertices, so that its not explored again.
targetId = vertex.edges.get(i).Target.vertexId;
if(!visited[targetId]) {
queue.add(vertex.edges.get(i).Target);
visited[targetId] = true;
}
}
}
}
Adjacency List Implementation
/*
* Demo Vertex class contains only vertexId.
* Can be extended to keep other details.
*/
public class Vertex {
int vertexId;
ArrayList<Edge> edges ;
public Vertex(int id) {
vertexId = id;
edges = new ArrayList<>();
}
public void addEdge(Edge e) {
edges.add(e);
}
}
public class Edge {
Vertex Target;
int weight;
public Edge(Vertex Target, int weight) {
this.Target = Target;
this.weight = weight;
}
}
public class Graph {
/*
* @vertices, ArrayList of all vertices in a graph.
* @directed, boolean variable to store if graph is directed/undirected
* @totalVertices, Total number of vertices in a graph.
*/
Vertex vertices[];
boolean directed;
int totalVertices;
/*
* @param directed , boolean variable to keep if graph is directed.
* @param totalVertices, total number of vertices in a graph.
*/
public Graph(int totalVertices, boolean directed) {
this.totalVertices = totalVertices;
this.directed = directed;
vertices = new Vertex[totalVertices];
for(int i=0; i<totalVertices; i++)
vertices[i] = null;
}
/*
* @param target @param source, check if source and target vertex already present (!=null).
* if source/target vertex not present in graph then create it.
* Else add weighted edge from source to target vertex.
*/
public void addVertex(int source, int target, int weight) {
if(vertices[source] == null) {
vertices[source] = new Vertex(source);
}
if(vertices[target] == null) {
vertices[target] = new Vertex(target);
}
Vertex sourceVertex = vertices[source];
Vertex targetVertex = vertices[target];
sourceVertex.addEdge(new Edge(targetVertex,weight));
if(!directed) {
targetVertex.addEdge(new Edge(sourceVertex,weight));
}
}
}
Graph Introduction.
GRAPH
=====
A graph is a datastructure consisting a set of vertices |V| and a set of edges |E|.
Vertices usually represent an entity and it might hold additional data pertaining to this entity.
The relationship between 2 different entities is represented by an edge. So if there is some relation between vertex a and vertex b, then there is an edge between a and b.
Example of graphs:
World wide web.
Social networks.
Internet Routers etc.
TYPES OF GRAPH
==============
1. UNDIRECTED GRAPHS
A graph is called as undirected graph if the edges are not directed meaning, there is a 2 way path for an edge i.e. the edge that goes out of the vertex also lead to this vertex from the connected vertex.
For eg. Social Network graph, if a is freind of b then it is tacit that b is also friend of a. Hence for representing this relation, we use an undirected graph.
Edge between a and b, leads to b from a and also to a from b.
2. DIRECTED GRAPH
A graph is called directed graph/digraph if the edges have directions meaning, the edge that goes out of a vertex doesnot lead to this vertex from connected vertex.
For eg. consider road network, It is possible that there is a one way road between city a and city b, hence people can reach b from a but not a from b since the graphs are directed.
3. WEIGHTED GRAPH
A graph is called as weighted graph if some weight is assigned to the edges.
For eg, again condier road network, There are 2 ways to reach city b from city a, but one of the path is shorter than the other than to represent this, we assign weight to the edges connecting city b from city a, the path taking less time is assign less weight and path taking more time might be assing more weight.
GRAPH REPRESENTATION
====================
There are many ways to represent graphs:
1. Adjacency Matrix.
2. Adjacency List.
3. Incidence Matrix.
4. Incidence List.
=====
A graph is a datastructure consisting a set of vertices |V| and a set of edges |E|.
Vertices usually represent an entity and it might hold additional data pertaining to this entity.
The relationship between 2 different entities is represented by an edge. So if there is some relation between vertex a and vertex b, then there is an edge between a and b.
Example of graphs:
World wide web.
Social networks.
Internet Routers etc.
TYPES OF GRAPH
==============
1. UNDIRECTED GRAPHS
A graph is called as undirected graph if the edges are not directed meaning, there is a 2 way path for an edge i.e. the edge that goes out of the vertex also lead to this vertex from the connected vertex.
For eg. Social Network graph, if a is freind of b then it is tacit that b is also friend of a. Hence for representing this relation, we use an undirected graph.
Edge between a and b, leads to b from a and also to a from b.
2. DIRECTED GRAPH
A graph is called directed graph/digraph if the edges have directions meaning, the edge that goes out of a vertex doesnot lead to this vertex from connected vertex.
For eg. consider road network, It is possible that there is a one way road between city a and city b, hence people can reach b from a but not a from b since the graphs are directed.
3. WEIGHTED GRAPH
A graph is called as weighted graph if some weight is assigned to the edges.
For eg, again condier road network, There are 2 ways to reach city b from city a, but one of the path is shorter than the other than to represent this, we assign weight to the edges connecting city b from city a, the path taking less time is assign less weight and path taking more time might be assing more weight.
GRAPH REPRESENTATION
====================
There are many ways to represent graphs:
1. Adjacency Matrix.
2. Adjacency List.
3. Incidence Matrix.
4. Incidence List.
Wednesday 25 September 2013
Parity Checker
#include <iostream>
using namespace std;
int setParity(int n)
{
int number = 1;
number = number<<8 ;
return (n|number);
}
bool isParitySet(int n)
{
int number = 128;
if(number && n)
return true;
else
return false;
}
int countOnes(int n)
{
int number = 1;
int count = 0;
for(int i=0; i<7; i++)
{
if(number & n)
{
count++;
}
number = number<<1;
}
return count;
}
int main()
{
int n = 2;
if(countOnes(n) % 2 == 0)
{
if(isParitySet(n))
{
n = n ^ 128;;
}
cout<<n;
}
else
{
cout<<"INVALLID NUMBER";
}
system("pause");
}
Monday 23 September 2013
Longest Increasing Sub-sequence.
/*
Guess
=====
If including element i forms maximum length increasing sequence.
Sub-problem
===========
Prefix of input string X, X[:i] for all i < n.
Recurrence
==========
LIS(i) = 1 + max(LIS(j)) for all j < i and arr[i] > arr[j].
Running Time
============
For string of length n.
No. of sub-problems = O(n).
Time/subprolem = O(n) (check all j's less than i)
Running Time = O(n2).
*/
#include <iostream>
using namespace std;
#define MAX 100
int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60, 80 };
int size = sizeof arr/sizeof arr[0];
int DP[MAX];
int DP1[MAX];
int findMax(int a[], int n) {
int maxVal = a[0];
for(int i=1; i<=n; i++)
if(maxVal < a[i])
maxVal = a[i];
return maxVal;
}
//Bottom Up Approach.
int LIS() {
int i,j,maxVal;
//Every element is a Sequence of length 1.
for(i=0; i<size; i++)
DP[i] = 1;
for(i=1; i<size; i++) {
for(j=0; j<i; j++) {
if(arr[i] > arr[j]) {
DP[i] = max(DP[i] , DP[j] + 1);
}
}
}
//Pick Maximum of all LIS
maxVal = findMax(DP,size-1);
return maxVal;
}
//Top Down Approach.
int LISTopDown(int i) {
int maxVal;
if(i==0)
return 1;
if(DP1[i]) {
return DP1[i];
}
for(int j=0; j<i; j++) {
if(arr[j] < arr[i])
if(LISTopDown(j)+1 > DP1[i])
DP1[i] = LISTopDown(j)+1;
}
maxVal = findMax(DP1,i);
return maxVal;
}
int main() {
printf("%d",LIS());
printf("\n%d",LISTopDown(size-1));
return 0;
}
Steps of Dynamic Programming.
Steps of Dynamic Programming
- Define Sub problems
Break a problem into sub-problems.Usually this is the tough part, identifying sub problems is half job done. - Guess Part of solution.Guess a solution of the sub-problem and the trick is don't just try any guess, try them all.
- Recurrence Relation.
Most important step.Once you have identified the sub-problems, the recurrence relation will be trivial. - Recurse + MemoizeStep-4 and step-5 will follow once completed first 3 steps.
- Solve original Problem
Use solution to sub-problems to solve the original problem.
Running Time
Running Time = No. of Sub-problems . Time/sub-problem
Eg.
consider worked out example for Edit Distance Problem.
Given two strings X and Y and set of operations replace (R), insert (I) and delete (D) all at equal cost. Find minimum number of edits (operations) required to convert one string into another.
Sub-problem:
==========
Suffix of X => X[i:]
Suffix of Y => Y[j:]
Considering length of X (|X|) = m and length of Y(|Y|) = n.
Total No. of Sub-problems = O(|X||Y|) = O(mn).
Guess
=====
From current position 3 decisions can be taken,
Replace X[i] -> Y[j] and advance both i and j.
Insert Y[j] and advance j.
Delete X[i] and advance i.
Recurrence
========
At current position select the minimum cost operation, out of all 3 operations.
DP(i,j) = min( REPLACE_COST(X[i],Y[j]) + DP(i+1,j+1) , INSERT_COST(Y[j]) + DP(i,j+1), COST_DELETE(X[i] ) + DP(i+1,j))
Solve Original Problem
================
DP(m,n) = Minimum cost.
Running Time
=========
No. of Subproblems = O(mn)
Time/Subproblem = O(1).
Running Time = O(mn).
Sunday 22 September 2013
What is Dynamic Programming?
Dynamic
programming is a method for solving complex problems by breaking them down into
simpler subproblems.
Dynamic
programming takes advantage of the fact that while solving a problem many of
the sub-problems are encountered and solved multiple times.
If we store the solution of this sub-problem (Memo-ize)
then no need of solving the sub-problem again, instead we refer to the memory
location where the solution of the sub-problem is stored and get the solution.
Dynamic
programming solves each sub-problem only once (the very first time), next time
the same problem can be looked up in the memory.
A Naïve solution
often ignores this fact and solves the sub-problem each time it is encountered.
Dynamic
programming can be applied to problems exhibiting 2 properties:
- Overlapping Sub problemsA
recursive algorithm solving the problem should solve the same subproblems over
and over, rather than generating new subproblems.For example, consider recursive algorithm for generating Fibonacci Numbers.Fi+2 = Fi+1 + Fi
F5 = F4 + F3 , F6 = F5 + F4Here F4 is solved in both F5 and F6. - Optimal SubstructureSolution to a given optimization problem can be obtained by the combination of optimal solutions to its subproblems.
Dynamic
Programming algorithms are used for optimization problem, (eg. Finding shortest
path, minimum cost of multiplying matrices etc) where we need to maximize or
minimize certain behaviour.
Dynamic
programming is kind of exhaustive search, an intelligent brute force that examines
all possible ways to solve the problem and pick the best solution.
Dynamic
Programming can solve a problem in 2 ways:
- Memoization/Top-Down Approach:A problem is divided into sub-problem, and solution of each sub-problem is searched in look up table. If solution already exist then it is returned else the sub-problem is computed and the result is stored in the lookup table.Initially lookup table is initialized with NULL.
- Tabulation/Bottom Up Approachsolve the sub-problems first and then combine the solution of these sub-problems stored in lookup table to solve the problem. Solution to bigger and bigger sub-problems is generated iteratively and ultimately solution to the original problem is obtained.
Tuesday 3 September 2013
Pascal Triangle.
/*
* ALGORITHM : Dynamic Programming.
* Input size of triangle n.
* Allocate a 2-D array of size nxn.
* Recurrence relation C(n,k) = C(n-1,k-1) + C(n-1,k)
* Use 2-D matrix to store C(n,k) at arr[i][j].
* Time complexity O(n2) and O(n) extra space.
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#define CLR(a) memset(a,0,sizeof a)
using namespace std;
void printSpaces(int sp)
{
int i,j;
printf("\n");
for(i=0; i<sp; i++)
printf(" ");
}
void binomialCoefficient(int n)
{
int i,j;
int arr[n+1][n+1];
CLR(arr);
for(i=0; i<=n;i++)
{
for(j=0;j<= n ;j++)
{
if( j ==0 || i == j)
arr[i][j] = 1;
else
arr[i][j] = arr[i-1][j-1] + arr[i-1][j];
}
}
for(i=0;i<=n;i++)
{
printSpaces(n-i);
for(j=0;j<=i;j++)
printf("%d ",arr[i][j]);
}
}
int main()
{
int n;
while(true)
{
scanf("%d",&n);
if(n <= 0)
break;
binomialCoefficient(n);
}
}
/*
OUTPUT
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
*/
Monday 2 September 2013
MAX XOR
/*
* Given an array A of unsigned 32-bit ints, choose two in-bounds indices i, j so as to maximize the value of A[i] ^ A[j], where ^ is the bitwise XOR (exclusive OR) operator.
* If there are multiple possible answers, print any one.
* Example Input:
* 4 2 0 13 49
* Output:
* 3 4
* Explanation: 13 ^ 49 is 60, 13 and 49 are positioned at indexes 3 and 4. Printing "4 3" would have been equally valid.
* Solution Guidance:
* Let k be the bit width (maximum number of bits) of the primitive.
* Easy: O(arr.length^2) time, O(1) space.
* Hard: Sub-quadratic complexity. An O(k*arr.length) time algorithm is possible. It is OK to use some extra space.
*/
#include <iostream>
using namespace std;
class node
{
int val;
bool isLeaf;
node *left;
node *right;
public:
node()
{
val = 0;
isLeaf = false;
left = NULL;
right = NULL;
}
void setVal(int n)
{
val = n;
}
int getVal()
{
return val;
}
void setLeftChild(node *ptr)
{
left = ptr;
}
void setRightChild(node *ptr)
{
right = ptr;
}
node* getLeftChild()
{
return left;
}
node* getRightChild()
{
return right;
}
void setIsLeaf(bool b)
{
isLeaf = b;
}
bool getIsLeaf()
{
return isLeaf;
}
};
class Tree
{
node *root;
int heightOfTree ;
public:
Tree()
{
root = new node();
root->setVal(99);
heightOfTree = 31;
}
int getMSBPosition()
{
return 0;
}
void insertNode(node* ptr, int n, int pos)
{
if(pos>=0)
{
int getBit = (1<<pos) & n;
node* newNode;
if(getBit)
{
if(ptr->getRightChild() == NULL)
{
newNode = new node();
newNode->setVal(1);
ptr->setRightChild(newNode);
}
if(pos == 0)
{
node* leafNode = new node();
newNode->setIsLeaf(true);
leafNode->setVal(n);
newNode->setLeftChild(leafNode);
}
else
insertNode(ptr->getRightChild(),n,pos-1);
}
else
{
if(ptr->getLeftChild() == NULL)
{
newNode = new node();
newNode->setVal(0);
ptr->setLeftChild(newNode);
}
if(pos == 0)
{
node* leafNode = new node();
leafNode->setVal(n);
newNode->setIsLeaf(true);
newNode->setLeftChild(leafNode);
}
else
insertNode(ptr->getLeftChild(),n,pos-1);
}
}
}
void insert(int n)
{
insertNode(root,n,heightOfTree);
}
int findMax(node* ptr1, node* ptr2)
{
if(ptr1->getIsLeaf() == false)
{
int n01 = 0;
int n10 = 0;
bool pathTaken = false;
if(ptr1->getLeftChild() != NULL && ptr2->getRightChild() != NULL)
{
n01 = findMax(ptr1->getLeftChild(),ptr2->getRightChild());
pathTaken = true;
}
if(ptr1->getRightChild() != NULL && ptr2->getLeftChild() != NULL)
{
n10 = findMax(ptr1->getRightChild(),ptr2->getLeftChild());
pathTaken = true;
}
if(!pathTaken)
{
if(ptr1->getLeftChild() && ptr2->getLeftChild())
n01 = findMax(ptr1->getLeftChild(),ptr2->getLeftChild());
else
n10 = findMax(ptr1->getRightChild(),ptr2->getRightChild());
}
return n01>n10?n01 : n10;
}
else
{
return ptr1->getLeftChild()->getVal() ^ ptr2->getLeftChild()->getVal();
}
}
int findMaxValue()
{
return findMax(root,root);
}
};
int maxValue(int *arr,int n)
{
int max = 0;
for(int i=0; i<n-1; i++)
{
for(int j=0; j<n; j++)
{
if(max < (arr[i]^arr[j]))
max = (arr[i]^arr[j]);
}
}
return max;
}
int main()
{
int numberOfElements;
cout<<"\nNUMBER OF ELEMENTS : ";
cin>>numberOfElements;
Tree t ;
int *arr = new int[numberOfElements];
for(int i=0; i<numberOfElements;i++)
{
cin>>arr[i];
t.insert(arr[i]);
}
cout<<"\nEASY = "<<maxValue(arr,numberOfElements);
cout<<"\nHARD = "<<t.findMaxValue();
}
FILL BITS
/*
* Consider a new bitwise binary operator that we will denote as x $ y. The result of this operator is that the set bits of x "flood outwards" y bits to both the left and the right.
* More precisely, the i-th bit (the least significant bit is considered to be the 0-th) of x $ y will be 1 if and only if x has any bit whose value is 1 and whose position differs by at most y from i (it can differ in either direction).
*
* Write a program that given unsigned ints x and y, computes x $ y.
* Example Inputs:
* 8 2
* 8 4
* 17 1
* Outputs (respectively):
* 62
* 255
* 59
* Explanation:
* In the first case, 8 is 0000..00001000 in binary. The operation causes the only set bit in the number to spread 2 positions in each direction, with a final result of 111110 (original bit underlined), which is 62 in decimal.
* In the second case, we spread the same bit 4 positions in each direction. This results in 4 1s to the left of the original bit's position. All 3 available positions to the right of the original bit's position are filled (a 4th would normally be filled, but we have reached the end of the number). The final number is 11111111, the value of which is 255.
* In the third case, 17 is 10001 in binary, and spreading the 1s in each direction by 1 gives 111011, which is 59 in decimal.
*
* Solution Guidance:
* Let k be the bit width (maximum number of bits) of the primitive.
* Moderate: O(k*y) time.
* Moderate: O(y) time.
* Hard: O(log(y)) time.
*/
#include <iostream>
using namespace std;
int getFillBitsMODERATE(int x,int y)
{
int mask = x;
for(int i=1; i<=y; i++)
mask |= mask<<1 | mask >> 1;
return mask;
}
int getFillBitsHARD(int x, int y)
{
int mask = x;
do
{
if(y%2)
{
mask |= mask<<1 | mask >>1;
y--;
}
y/=2;
mask |= mask<<y | mask >>y;
}while(y>0);
return mask;
}
int main()
{
int x = 8;
int y = 2;
int testCases;
cin>>testCases;
for(int i=0; i<testCases; i++)
{
cout<<"\n\nENTER NUMBERS : ";
cin>>x>>y;
cout<<"\nEASY : "<<getFillBitsMODERATE(x,y);
cout<<"\nHARD : "<<getFillBitsHARD(x,y);
}
}
RANGE OPERATION
/*
* Let us define A(m, n) = m & (m+1) & ... & (n-1) & n, where & is the bitwise AND operation.
* Write a program that, given 64-bit unsigned longs m and n, computes A(m, n).
* Example Inputs:
* 49 54
* 2 2
* 2 3
* Outputs (respectively):
* 48
* 2
* 2
* Explanation:
* A(49, 54) = 49 & 50 & 51 & 52 & 53 & 54 = 48
* A(2, 2) = 2. If m = n, A(m, n) = m = n.
* A(2, 3) = 2 & 3 = 2
* 3
* Solution Guidance:
* Let k be the bit width (maximum number of bits) of the primitive.
* Easy: O(n - m) time. Consider that since m and n can be any 64-bit numbers, this could be
* huge.
* Moderate-Hard: O(k) time.
* Hard: O(log(k)) time.
*/
#include <iostream>
using namespace std;
int RangeOperationEASY(long long int m,long long int n)
{
long long int result = n;
n--;
for(;n>=m; n--)
{
result &= n;
}
return result;
}
long long int getNextHighestPower(long long int diff)
{
long long int pow = 0;
while(true)
{
if(diff > (1<<pow))
pow++;
else
return pow;
}
}
long long int getNextHighestPowerlogn(long long int diff)
{
diff--;
diff |= diff >> 1;
diff |= diff >> 2;
diff |= diff >> 4;
diff |= diff >> 8;
diff |= diff >> 16;
diff |= diff >> 32;
diff++;
return diff;
}
long long int RangeOperationHARD(long long int m, long long int n)
{
long long int result = m & n;
long long int diff = n-m+1;
long long int mask = ~(getNextHighestPowerlogn(diff)-1);
return result & mask;
}
int main()
{
long long int m;
long long int n;
int testCases;
cin>>testCases;
for(int i=0; i<testCases; i++)
{
cin>>m>>n;
cout<<"\nEASY : "<<RangeOperationEASY(m,n);
cout<<"\nHARD : "<<RangeOperationHARD(m,n)<<endl;
}
}
COUNT BITS
/*
* Given a 64-bit signed number, count the number of bits that are set to 1.
* Bonus: In addition to the obvious approach, continue exploring till you find other efficient approaches.
*
* Example Inputs:
* 0
* -1
* 14
* Outputs (respectively):
* 0
* 64
* 3
*
* Solution Guidance:
* Let k be the bit width (maximum number of bits) of the primitive.
* Easy: O(k) time.
* Moderate: O(number of bits whose value is 1) time.
* Very Hard: O(log(k)) time
*/
#include <iostream>
using namespace std;
inline bool isSet(long long int n,int i)
{
long long int x = 1;
x <<=i;
if(x&n)
return true;
return false;
}
int countBitsEASY(long long int n)
{
int size = sizeof(n)*8;
int count = 0;
for(int i=0; i<size; i++)
{
if(isSet(n,i))
count++;
}
return count;
}
int countBitsMODERATE(long long int n)
{
int size = sizeof(n) * 8;
int count = 0;
if(n<0)
{
n &= n^(1LL<<size-1);
count = 1;
}
for(; n > 0; count++)
n &= n-1;
return count;
}
//found it to be Hamming weight problem on wiki.
int countBitsVERYHARD(long long int n)
{
long long int result = (n & 0x5555555555555555LL) + (n>>1 & 0x5555555555555555LL);
result = (result & 0x3333333333333333LL) + ((result>>2) & (0x3333333333333333LL));
result = (result & 0x0f0f0f0f0f0f0f0fLL) + ((result>>4) & (0x0f0f0f0f0f0f0f0fLL));
result = (result & 0x00ff00ff00ff00ffLL) + ((result>>8) & (0x00ff00ff00ff00ffLL));
result = (result & 0x0000ffff0000ffffLL) + ((result>>16)& (0x0000ffff0000ffffLL));
result = (result & 0x00000000ffffffffLL) + ((result>>32)& (0x00000000ffffffffLL));
return result;
}
int main()
{
long long int n = 15;
int testCases ;
cin>>testCases;
for(int i=0; i<testCases; i++)
{
cin>>n;
cout<<"\nEASY : "<<countBitsEASY(n);
cout<<"\nMODERATE : "<<countBitsMODERATE(n);
cout<<"\nVERY HARDS : "<<countBitsVERYHARD(n)<<endl;
}
}
HIT BIT
/*
* Given a 64-bit signed long, find the position of the most significant set bit (a "set bit" means a bit whose value is 1). The least significant bit is considered to have position 0, the next least significant bit has position 1, and so on.
* If there are no set bits at all, print -1.
* Example Inputs:
* 0
* -1
* 25
* Outputs (respectively):
* -1
* 63
* 4
* Solution Guidance:
* Let k be the bit width (maximum number of bits) of the primitive.
* Easy: O(k) time.
* Moderate: O(log(k)) time.
*/
#include <iostream>
using namespace std;
inline bool isSet(long long int n,int i)
{
long long int x = 1;
x <<=i;
if(x&n)
return true;
return false;
}
//EASY
int getSetMSBPositionEASY(long long int n)
{
int size = sizeof(n);
size <<=3;
for(int i=size-1; i>=0; i--)
{
if(isSet(n,i))
return i;
}
return -1;
}
//MODERATE
int getSetMSBPositionMODERATE(long long int n)
{
int size = sizeof(n);
size <<=3;
int start = size-1;
int end = 0;
int mid = (start+end)/2;
while( start >= end)
{
long long int check = ~(0LL)^((1LL<<mid)-1);
if(n & check)
{
end = mid+1;
}
else
{
start = mid-1;
}
mid= (start+end)/2;
}
return mid;
}
int main()
{
long long int n;
int testCases;
//FIRST ENTER NUMBER OF TEST CASES
cin>>testCases;
for(int i=0; i<testCases; i++)
{
cin>>n;
if(!n)
cout<<-1;
else
{
cout<<"\nEASY = "<<getSetMSBPositionEASY(n);
cout<<"\nMODERATE = "<<getSetMSBPositionMODERATE(n);
}
}
}
Sunday 14 July 2013
You are given an array of n integers which can contain integers from 1 to n only . Some elements can be repeated multiple times and some other elements can be absent from the array . Write a running code on paper which takes O(1) space apart from the input array and O(n) time to print which elements are not present in the array and the count of every element which is there in the array along with the element number .
/*
First Let's see what all approaches we can take and then we check if it fits our requirement.
1. Brute Force: Select an element from 1 to N and check it frequency of occurrence. But this will be O(n2) and not O(n) .
2. XOR : but this technique won't work as question mentions an element can be repeated multiple times. so if element repeats 2 times or 4 times each time result of xor will be 0 so we cannot get the frequency of occurrences.
3. HashMap : We can create a HashMap in O(n) key will be elements and value will be their frequency of occurrence. But since we have to do it in O(1) space we cannot take this approach.
So we cannot opt for any of the above 3 approach. We have to check for some 4th approach.
Since we have range of numbers given to us we have to think in those lines.
Array Index is from 0 to N-1 and range is from 1 to N. Can't we use the array as hash itself?
where array "Index-1" represents the key (element) and value stored at index will represent the "frequency of occurrence".
But how will we take care that an element present at any index is not overwritten as this can cause problem?
We can sort the array in that case value present at index i is I+1 itself.
What is the complexity of sorting the array?
since the range of element is given to us we can sort it in O(n).
ALGORITHM
Since array contains elements from 1 to N we cannot keep frequency in same array as it will confuse which one is frequency and which one is the element value.
To overcome this, store frequency in negative, -1 = element appear once and so on, by this we are able to distinguish between frequency of occurrence and elements.
Negative values/0 are frequency and +ve values are elements.
1. Scan array from left to right.
Pos =0 ; while pos < N
2. If current element is –ve or 0 then move forward (pos++).
3. Desiredpos = arr[pos]-1.
4. Check if arr[desiredPos] > 0
a. If yes that means no previous occurrence of current element.
Hence copy arr[pos] = arr[desiredPos] and set arr[desiredPos] =-1 i.e. first occurrence.
b. Else if it is encountered earlier also then decrement the frequency (arr[desiredPos]--) and set arr[pos] =0.
5. While displaying frequency multiply the elements with -1, as all elements in array will be either –ve or 0.
*/
#include <iostream>
using namespace std;
void getDuplicate(int arr[],int size)
{
int pos = 0;
int desiredPos = 0;
while(pos < size)
{
if(arr[pos] <= 0)
{
pos++;
continue;
}
desiredPos = arr[pos] -1;
if(arr[desiredPos] > 0)
{
arr[pos] = arr[desiredPos];
arr[desiredPos] = -1;
}
else
{
arr[desiredPos]--;
arr[pos] = 0;
pos++;
}
}
}
void display(int arr[], int size)
{
for(int i=0; i<size; i++)
cout<<"\nElement = "<<i+1<<"\tFrequency = "<<arr[i]*-1;
}
int main()
{
int arr[] = {6,4,1,4,3,2,5,2,1};
int size = sizeof(arr)/sizeof(arr[0]);
getDuplicate(arr,size);
display(arr,size);
}
Print all the words in a 3x3 matrix 'c','b','k' ..... 'd','a','l' ...... 'g','t','i' . words can be found horizontally, vertically and diagonally (reverse/straight order).
/*
An alphabet can be used only in one of the word.
If any cell of matrix constitutes to any word, I have replaced the character with a '*'
*/
#include <iostream>
#include <sstream>
using namespace std;
const int DIM = 3;
const int MAXNEIGHBOURS = 8;
int displacement[8][2] = {{-1,-1},{0,-1},{1,-1},{1,0},{-1,1},{0,1},{-1,1},{-1,0}};
char matrix[DIM][DIM] = {{'c','a','t'},{'a','j','i'},{'t','n','o'}};
void displayMatrix();
bool isValid(int row, int col)
{
if(row<0 || col <0 || row >= DIM || col >= DIM)
return false;
if(matrix[row][col] == '*')
return false;
return true;
}
bool solveMatrix(int row,int col, string word)
{
if(word.compare("*") ==0)
return false;
if(dictionary.search(word))
{
cout<<"\n"<<word;
matrix[row][col] = '*';
return true;
}
for(int i=0; i<MAXNEIGHBOURS ; i++)
{
int newRow = row + displacement[i][0];
int newCol = col + displacement[i][1];
char originalCharacter = matrix[row][col];
matrix[row][col] = '*';
if(isValid(newRow,newCol))
{
if(solveMatrix(newRow,newCol,word+matrix[newRow][newCol]))
return true;
}
matrix[row][col] = originalCharacter;
}
return false;
}
string toString(char ch)
{
stringstream ss;
string s;
ss<<ch;
ss>>s;
return s;
}
int main()
{
dictionary.insert("hello");
dictionary.insert("cat");
dictionary.insert("in");
dictionary.insert("no");
dictionary.insert("at");
for(int i=0; i<DIM; i++)
for(int j=0; j<DIM; j++)
solveMatrix(i,j,toString(matrix[i][j]));
cout<<endl;
system("pause");
}
/*
I have used TRIE to store dictionary below is the implentation of it.
*/
class TRIENode
{
public:
bool word;
int prefixCount;
TRIENode *child[26];
TRIENode()
{
word = false;
prefixCount = 0;
for(int i=0; i<26; i++)
child[i] = NULL;
}
bool isWord()
{
return word;
}
};
class TRIE
{
private:
TRIENode *headNode;
public:
TRIE()
{
headNode = new TRIENode();
}
void insert(string w)
{
TRIENode *ptr = headNode;
ptr->prefixCount++;
for(int i=0; i<w.length(); i++)
{
int index = w[i] - int('a');
if(ptr->child[index] ==NULL)
{
ptr->child[index] = new TRIENode();
}
ptr->child[index]->prefixCount++;
ptr = ptr->child[index];
}
ptr->word = true;
}
bool search(string str)
{
TRIENode *ptr = headNode;
for(int i=0; i<str.length(); i++)
{
int index = str[i] - 'a';
if(ptr->child[index] == NULL)
return false;
ptr = ptr->child[index];
}
if(ptr->isWord())
return true;
return false;
}
}dictionary;
Monday 8 July 2013
Given a sorted rotated array, find an element in O(logn) time without finding the pivot element.
//============================================================================
// Name : SortedRotatedArray.cpp
// Author : Varun Sharma
// Version : 1.0
// Complexity : O(logn)
// Description : Finding Element in a sorted rotated array, without finding pivot.
//============================================================================
/*
ALGORITHM
=========
1. Initialize start = 0, end = size-1.
2. Repeat while start <= end
a. Calculate mid element => mid = (start+end)/2.
b. If arr[mid] = val then print position and return true.
c. Array is sorted from start to mid or from mid to end, check which one is the case.
d. Sorted from Mid to end: arr[mid] < arr[end].
i. If search value lies in right sorted half : val arr[mid] && val <= arr[end]
then start = mid+1
ii.Else end = mid-1
e. Else Sorted from start to mid .
i. If search value lies in left sorted half: val <arr[mid] && val>= arr[start]
then end = mid-1
ii.Else start = mid+1.
3. Return false if element not found.
*/
#include <iostream>
using namespace std;
bool search(int arr[],int size,int val) {
int start = 0;
int end = size-1;
int mid;
while(start <= end) {
mid = (start+end)/2;
//Value at mid == search value then return found.
if(arr[mid] == val) {
cout<<"nFOUND AT POSITION : "<<mid+1;
return true;
}
//If value at mid < value at end
//i.e. Array is sorted from mid to end.
if(arr[mid] < arr[end]) {
//Value lies in right sorted half of array.
if(val > arr[mid] && val <= arr[end])
start = mid+1;
else
//Value lies in left half of array.
end = mid-1;
}
//Array is sorted from start to mid.
else {
//Value lies in left sorted half of array.
if(val < arr[mid] && val >= arr[start])
end = mid-1;
//Value lies in right sorted half.
else
start = mid+1;
}
}
return false;
}
int main() {
int arr[] = {6,7,8,9,10,11,1,2,3,4,5};
int size = sizeof arr/sizeof arr[0];
if(!search(arr,size,6))
cout<<"nVALUE DOESN'T EXIST";
int arr1[] = {6,7,8,9,10,11,12,13,14,5};
int size1 = sizeof arr1/sizeof arr1[0];
if(!search(arr1,size1,5))
cout<<"nVALUE DOESN'T EXIST";
int arr2[] = {5,6,7,8,9,10,11,12,13,14};
int size2 = sizeof arr2/sizeof arr2[0];
if(!search(arr2,size2,5))
cout<<"nVALUE DOESN'T EXIST";
int arr3[] = {5,6,7,8,9,10,11,12,13,14};
int size3 = sizeof arr3/sizeof arr3[0];
if(!search(arr3,size3,18))
cout<<"nVALUE DOESN'T EXIST";
int arr4[] = {6,7,8,9,10,11,12,13,14,5};
int size4 = sizeof arr4/sizeof arr4[0];
if(!search(arr4,size4,1))
cout<<"nVALUE DOESN'T EXIST";
return 0;
}
Sunday 7 July 2013
Convert Infix expression to Post/Pre fix.
/*
* Compiler always represent expression in postfix Notation.
* Shunting yard algorithm is used for this conversion.
* It can be used to convert to Prefix also.
* Reverse Input string.
* Use shunting yard algorith.
* Reverse the output string
*/
#include <iostream>
#include <stack>
using namespace std;
string output = "";
stack<int> operatorStack;
// Attach integer value with each operand.
// Same precedence operator share same int. value.
// ( paren has least value.
int getPrecedence(char ch)
{
switch(ch)
{
case '*' : return 2;
case '+' : return 1;
case '/' : return 2;
case '-' : return 1;
case '(' : return 0;
}
}
// Get precedence of current as well as stack top element.
// If current precedence is greater or equal then return true
// else return false
bool greaterPrecedenceThanStackTop(char ch)
{
int topPrecedence = getPrecedence(operatorStack.top());
int charPrecedence = getPrecedence(ch);
if(charPrecedence >= topPrecedence)
return true;
return false;
}
bool isOperand(char ch)
{
switch(ch)
{
case '+' : return true;
case '-' : return true;
case '*' : return true;
case '/' : return true;
default : return false;
}
}
bool isParen(char ch)
{
if(ch == '(' || ch == ')')
return true;
return false;
}
// If opening paren push it to operator stack.
// Else Pop operators from operator stack to output string.
// until operning paren is popped.
void scannedParen(char ch)
{
if(ch == '(')
{
cout<<"\n\tPUSH ( TO OPERATOR STACK";
operatorStack.push(ch);
}
else
{
while(!operatorStack.empty() && operatorStack.top() != '(')
{
cout<<"\n\tPOP AND ADD TO OUTPUT "<<char(operatorStack.top());
output += operatorStack.top();
operatorStack.pop();
}
if(!operatorStack.empty())
{
cout<<"\n\tPOP (";
operatorStack.pop();
}
}
}
// If stack is empty push operator.
// If operator has same or higher precedence than stack[top] push operator.
// Else pop operators until stack is empty or stack[top] has equal or less precedence
// Than current operator.
void scannedOperator(char ch)
{
if(operatorStack.empty())
{
cout<<"\n\tPUSH TO OPERATOR STACK";
operatorStack.push(ch);
return;
}
if(greaterPrecedenceThanStackTop(ch))
{
cout<<"\n\tPUSH TO OPERATOR STACK";
operatorStack.push(ch);
}
else
{
while(!greaterPrecedenceThanStackTop(ch) && !operatorStack.empty())
{
cout<<"\n\tPOP "<<char(operatorStack.top());
output += operatorStack.top();
operatorStack.pop();
}
cout<<"\n\tPUSH "<<ch;
operatorStack.push(ch);
}
}
//Copy all operators from operatroStack to output string.
void flushStack()
{
while(!operatorStack.empty())
{
char c = operatorStack.top();
cout<<"\n\tCOPY "<<c<<" TO OUTPUT";
operatorStack.pop();
if(c == '(')
continue;
output += c;
}
}
//Separate operators, parenthesis and Operands.
//Call appropriate function accordingly.
void scanInput(string input)
{
string operand = "";
for(int i=0 ; i< input.length(); i++)
{
char ch = input[i];
cout<<"\n\nCURRENT CHAR = "<<ch;
if(isParen(ch))
{
output += operand;
operand = "";
scannedParen(ch);
}
else if(isOperand(ch))
{
output += operand;
operand = "";
scannedOperator(ch);
}
else
{
cout<<"\n\tCOPY TO OUTPUT STRING";
operand += ch;
}
}
cout<<"\n\nEND OF INPUT : FLUSH STACK";
output += operand;
flushStack();
}
int main()
{
string input = "a+(b+c*(e/f)+d)*g";
cout<<"INFIX NOTATION : "<<input;
scanInput(input);
cout<<"\n\nPOSTFIX NOTATION : "<<output<<endl;
system("pause");
}
/*
OUTPUT
-------
INFIX NOTATION : a+(b+c*(e/f)+d)*g
CURRENT CHAR = a
COPY TO OUTPUT STRING
CURRENT CHAR = +
PUSH TO OPERATOR STACK
CURRENT CHAR = (
PUSH ( TO OPERATOR STACK
CURRENT CHAR = b
COPY TO OUTPUT STRING
CURRENT CHAR = +
PUSH TO OPERATOR STACK
CURRENT CHAR = c
COPY TO OUTPUT STRING
CURRENT CHAR = *
PUSH TO OPERATOR STACK
CURRENT CHAR = (
PUSH ( TO OPERATOR STACK
CURRENT CHAR = e
COPY TO OUTPUT STRING
CURRENT CHAR = /
PUSH TO OPERATOR STACK
CURRENT CHAR = f
COPY TO OUTPUT STRING
CURRENT CHAR = )
POP AND ADD TO OUTPUT /
POP (
CURRENT CHAR = +
POP *
PUSH +
CURRENT CHAR = d
COPY TO OUTPUT STRING
CURRENT CHAR = )
POP AND ADD TO OUTPUT +
POP AND ADD TO OUTPUT +
POP (
CURRENT CHAR = *
PUSH TO OPERATOR STACK
CURRENT CHAR = g
COPY TO OUTPUT STRING
END OF INPUT : FLUSH STACK
COPY * TO OUTPUT
COPY + TO OUTPUT
POSTFIX NOTATION : abcef/*d++g*+
*/
Wednesday 3 July 2013
Given a number, return the next multiple of 64 that follows it, using bit operations and no loops. e.g input = 90, return 128.
#include <iostream>
using namespace std;
int main()
{
int n = 90;
int n1 = n>>6;
int n2 = (n1+1)<<6;
cout<<n2;
system("pause");
}
Wednesday 26 June 2013
#include <iostream>
using namespace std;
#define HEIGHT 25
#define WIDTH 80
char Matrix[HEIGHT][WIDTH];
double findSlope(int x1,int x2, int y1, int y2)
{
if(x1 == x2)
return 0;
return (double(y2-y1)/double(x2-x1));
}
void initializeMatrix()
{
for(int i=0; i<HEIGHT; i++)
{
for(int j=0; j<WIDTH; j++)
{
Matrix[i][j] = '.';
}
}
}
int roundToInt(float val)
{
if(val - int(val) < 0.5)
return int(val);
return int(val+1);
}
void setPoint(float slope,float constant,int x)
{
int y = roundToInt(slope * x + constant);
if(y >=0 && y < HEIGHT)
{
Matrix[x][y] = '*';
}
}
void fillArray(float slope,float constant,int x1,int x2, int y1, int y2)
{
for(int x=0; x < WIDTH; x++)
{
setPoint(slope,constant,x);
}
}
float findConstant(float slope,int x1,int y1)
{
return (y1 - slope * x1);
}
void displayMatrix()
{
for(int row=0; row<HEIGHT; row++)
{
cout<<"\n"<<row<<" = ";
for(int col = 0; col<WIDTH; col++)
{
cout<<" "<<Matrix[row][col];
}
}
}
int main()
{
int x1,x2,y1,y2;
x1= 10;
y1= 20;
x2= 20;
y2= 30;
float slope= findSlope(x1,x2,y1,y2);
float constant = findConstant(slope,x1,y1);
initializeMatrix();
fillArray(slope,constant,x1,x2,y1,y2);
displayMatrix();
system("pause");
}
using namespace std;
#define HEIGHT 25
#define WIDTH 80
char Matrix[HEIGHT][WIDTH];
double findSlope(int x1,int x2, int y1, int y2)
{
if(x1 == x2)
return 0;
return (double(y2-y1)/double(x2-x1));
}
void initializeMatrix()
{
for(int i=0; i<HEIGHT; i++)
{
for(int j=0; j<WIDTH; j++)
{
Matrix[i][j] = '.';
}
}
}
int roundToInt(float val)
{
if(val - int(val) < 0.5)
return int(val);
return int(val+1);
}
void setPoint(float slope,float constant,int x)
{
int y = roundToInt(slope * x + constant);
if(y >=0 && y < HEIGHT)
{
Matrix[x][y] = '*';
}
}
void fillArray(float slope,float constant,int x1,int x2, int y1, int y2)
{
for(int x=0; x < WIDTH; x++)
{
setPoint(slope,constant,x);
}
}
float findConstant(float slope,int x1,int y1)
{
return (y1 - slope * x1);
}
void displayMatrix()
{
for(int row=0; row<HEIGHT; row++)
{
cout<<"\n"<<row<<" = ";
for(int col = 0; col<WIDTH; col++)
{
cout<<" "<<Matrix[row][col];
}
}
}
int main()
{
int x1,x2,y1,y2;
x1= 10;
y1= 20;
x2= 20;
y2= 30;
float slope= findSlope(x1,x2,y1,y2);
float constant = findConstant(slope,x1,y1);
initializeMatrix();
fillArray(slope,constant,x1,x2,y1,y2);
displayMatrix();
system("pause");
}
Monday 24 June 2013
Program to get the number and print the number in words (number <= 99999). For eg. 1234 is one thousand two hundred thirty four.
#include <iostream>
#include <sstream>
using namespace std;
string unit[] = {"","one","two","three","four","five","six","seven","eight","nine"};
string teen[] = {"","eleven","twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen","nineteen"};
string ty[] = {"","ten","twenty","thirty","forty","fifty","sixty","seventy","eighty","ninety"};
int countDigits(int n)
{
int count = 0;
while(n)
{
n/= 10;
count++;
}
return count;
}
string numToString(int n)
{
string result ;
ostringstream r;
r<<n;
result = r.str();
return result;
}
void print10000(int d1,int d2)
{
if(d1 > 1)
{
cout<<ty[d1]<<" ";
cout<<unit[d2]<<" ";
}
else
{
if(d2)
cout<<teen[d1]<<" ";
else
cout<<"Ten ";
}
cout<<"thousand ";
}
void print1000(int d)
{
if(d)
{
cout<<unit[d]<<" thousand ";
}
}
void print100(int d)
{
if(d)
{
cout<<unit[d]<<" hundred ";
}
}
void print10(int d1,int d2)
{
if(d1)
{
if(d1 > 1)
{
cout<<ty[d1]<<" ";
cout<<unit[d2]<<" ";
}
else if(d2)
cout<<teen[d2];
else
cout<<"Ten";
}
else if(d2)
{
cout<<unit[d2];
}
}
string lengthFive(string number)
{
int digit5,digit4,digit3,digit2,digit1;
cout<<"Number is "<<number<<"\n";
digit1 = number[4] - 48;
digit2 = number[3] - 48;
digit3 = number[2] - 48;
digit4 = number[1] - 48;
digit5 = number[0] - 48;
print10000(digit5,digit4);
print100(digit3);
print10(digit2,digit1);
}
string lengthFour(string number)
{
int digit4 = number[0] - 48;
int digit3 = number[1] - 48;
int digit2 = number[2] - 48;
int digit1 = number[3] - 48;
print1000(digit4);
print100(digit3);
print10(digit2,digit1);
}
string lengthThree(string number)
{
int digit3 = number[0] - 48;
int digit2 = number[1] - 48;
int digit1 = number[2] - 48;
print100(digit3);
print10(digit2,digit1);
}
string lengthTwo(string number)
{
int digit2 = number[0] - 48;
int digit1 = number[1] - 48;
print10(digit2,digit1);
}
string lengthOne(string number)
{
int digit1 = number[0] - 48;
cout<<unit[digit1];
}
int main()
{
int n = 10002;
if(!n)
{
cout<<"zero";
return 0;
}
int len = countDigits(n);
string number = numToString(n);
switch(len)
{
case 1: lengthOne(number);break;
case 2: lengthTwo(number);break;
case 3: lengthThree(number);break;
case 4: lengthFour(number);break;
case 5: lengthFive(number);break;
default: cout<<"Invalid";
}
system("pause");
}
Sunday 23 June 2013
Checking Parity.
#include <iostream>
using namespace std;
int setParity(int n)
{
int number = 1;
number = number<<8 ;
return (n|number);
}
bool isParitySet(int n)
{
int number = 128;
if(number && n)
return true;
else
return false;
}
int countOnes(int n)
{
int number = 1;
int count = 0;
for(int i=0; i<7; i++)
{
if(number & n)
{
count++;
}
number = number<<1;
}
return count;
}
int main()
{
int n = 2;
if(countOnes(n) % 2 == 0)
{
if(isParitySet(n))
{
n = n ^ 128;;
}
cout<<n;
}
else
{
cout<<"INVALLID NUMBER";
}
system("pause");
}
Parity Bit for 7-bit Integer.
#include <iostream>
using namespace std;
int setParity(int n)
{
int number = 1;
number = number<<7 ;
return (n|number);
}
int countOnes(int n)
{
int number = 1;
int count = 0;
for(int i=0; i<7; i++)
{
if(number & n)
{
count++;
}
number = number<<1;
}
return count;
}
int main()
{
int n = 11;
if(countOnes(n)%2 ==1)
n = setParity(n);
cout<<n;
system("pause");
}
Saturday 22 June 2013
Implementation of K-DTrees (2-D)
/*
* If all points are in k – dimensions then Select one of the dimension for a level.
* Get median element in selected dimension.
* Push all points smaller than median elements in left sub tree and all greater points in right sub tree.
* Recursively call the buildTree function with leftSubset and Set leftChild of curNode.
* Recursively call the buildTree function with rightSubset and set rightChild of curNode.
*/
#include <iostream>
#include <vector>
using namespace std;
class Point
{
public:
int x;
int y;
Point()
{
x = 0;
y = 0;
}
Point(int xp, int yp)
{
x = xp;
y = yp;
}
};
class TreeNode
{
public:
Point p;
TreeNode *left;
TreeNode *right;
TreeNode()
{
left = NULL;
right = NULL;
}
TreeNode(Point pt)
{
p = pt;
left = NULL;
right = NULL;
}
};
class KDTree
{
TreeNode *root;
public:
KDTree()
{
root = NULL;
}
TreeNode* getRoot()
{
return root;
}
TreeNode* createNode(Point ptr)
{
TreeNode *n = new TreeNode(ptr);
return n;
}
void CreateLeftRightSubset(vector <Point> PointSet, Point median, vector <Point> &leftSet, vector <Point> &rightSet, int depth)
{
// Check x coordinates
if(depth %2 == 0)
{
// Push all points having x coordinate
// less than median to leftSet and rest to right set
for(int i=0; i < PointSet.size() ; i++)
{
// Skip median.
if(PointSet[i].x == median.x && PointSet[i].y == median.y )
continue;
if(PointSet[i].x < median.x)
leftSet.push_back(PointSet[i]);
else
rightSet.push_back(PointSet[i]);
}
}
// Check y coordinates
else
{
// Push all points having y coordinate
// less than median to leftSet and rest to rightSet.
for(int i=0; i < PointSet.size() ; i++)
{
// Skip median.
if(PointSet[i].x == median.x && PointSet[i].y == median.y )
continue;
if(PointSet[i].y < median.y)
leftSet.push_back(PointSet[i]);
else
rightSet.push_back(PointSet[i]);
}
}
}
// Sort vector on x coordinates
void sortX(vector <Point> &PointSet);
// Sort vector on y coordinates
void sortY(vector <Point> &PointSet);
// Return median of all points in PointSet.
Point getMedian(vector <Point> &PointSet , int depth)
{
//Median of x coordinates.
if(depth % 2 ==0 )
{
sortX(PointSet);
Point M = PointSet[PointSet.size()/2];
// To prevent infinite recurrence
if(M.x > PointSet[0].x)
{
return M;
}
M.x = M.x+1;
return M;
}
//Median of y coordinates.
else
{
sortY(PointSet);
Point M = PointSet[PointSet.size()/2];
// TO prevent infinite recurrence
if(M.y > PointSet[0].y)
{
return M;
}
M.y = M.y+1;
return M;
}
}
TreeNode* buildTree(vector <Point> PointSet , int depth)
{
if(PointSet.size() == 1)
return (createNode(PointSet[0]));
Point M = getMedian(PointSet,depth);
TreeNode* curNode = createNode(M);
if(isEmpty())
root = curNode;
vector <Point> leftSet;
vector <Point> rightSet;
CreateLeftRightSubset(PointSet,M,leftSet,rightSet,depth);
if(leftSet.size() != 0)
curNode->left = buildTree(leftSet, depth+1);
if(rightSet.size() != 0)
curNode->right = buildTree(rightSet, depth+1);
return curNode;
}
};
int main()
{
vector <Point> v;
v.push_back(Point(6,1));
v.push_back(Point(5,5));
v.push_back(Point(9,6));
v.push_back(Point(3,6));
v.push_back(Point(4,9));
v.push_back(Point(4,0));
v.push_back(Point(7,9));
v.push_back(Point(2,9));
KDTree tree;
tree.buildTree(v,0);
tree.preorder(tree.getRoot());
system("pause");
}
Tuesday 18 June 2013
Print encoding for an Array: Rules: consider BST made from given array. Let say number x is present in the BST and to reach x, If you go right print 1, if left then 0.Now you are given an index i in the array A (so x = A[i]) and print the encoding without constructing BST to reach x and without space with least time complexity.
/*
ALGORITHM
1. Scan array from left to right.
2. Keep 2 variables min = INT_MIN and max = INT_MAX
min and max are used to keep track of whether the subtree of current node will store desired number searchNumber.
3. If value of current elements is between min and max, then subtree of this node will contain searchNumber.
4. If search number is less than current element, then update min = currentElement and print 1 since it will take right path.
5. If search number is greater than current element then update max = currentElement and print 0, since it will take left path.
COMPLEXITY
Time : O(n)
Space: O(1)
*/
#include <iostream>
#include <climits>
using namespace std;
int main()
{
int a[]={50,30,10,20,70,60,55,65,63,80};
int searchNumber = 63;
int size = sizeof(a)/sizeof(a[0]);
int min = INT_MIN;
int max = INT_MAX;
for(int i=0; i<size && a[i] != searchNumber ; i++)
{
if(a[i] >min && a[i] < max)
{
if(a[i] < searchNumber)
{
min = a[i];
cout<<" 1";
}
else
{
max = a[i];
cout<<" 0";
}
}
}
system("pause");
}
Sunday 16 June 2013
Implementation of SkipList Datastructure.
#include <iostream>
#include <climits>
using namespace std;
class skipNode
{
private:
int data;
int height;
skipNode **forward;
public:
skipNode(int d,int h)
{
data = d;
height = h;
forward = new skipNode*[height];
}
// Return max height of skipList Node.
int getHeight()
{
return height;
}
// Set data value of skipList Node.
void setData(int number)
{
data = number;
}
// Return Data value of skipList Node.
int getData()
{
return data;
}
// Set forward[pos] = ptr
void setForwardLink(skipNode *ptr, int pos)
{
forward[pos] = ptr;
}
// Return forward[index]
skipNode* getForwardLink(int index)
{
return forward[index];
}
};
class skipList
{
private:
int maxHeight;
skipNode *head;
skipNode *tail;
// static int count to be used as seed to srand
static int count;
public:
skipList()
{
maxHeight = 5;
head = new skipNode(INT_MIN,maxHeight);
tail = new skipNode(INT_MAX,maxHeight);
for(int i=0; i<maxHeight; i++)
{
head->setForwardLink(tail,i);
tail->setForwardLink(NULL,i);
}
}
// Generate a random number betweem 1 - maxHeight.
int getHeight()
{
count++;
srand(count);
return ((rand() % maxHeight) +1);
}
// Traverse and print all nodes at a level.
void levelTraversal()
{
for(int level = maxHeight-1; level >=0 ; level--)
{
cout<<"nLevel = "<<level;
skipNode *next = head->getForwardLink(level);
while(next != tail )
{
cout<<"t"<<next->getData();
next = next->getForwardLink(level);
}
}
}
void insertNode(int val)
{
// Check if already Present.
if(searchNode(val))
{
return;
}
// If not get Random height for New Node.
int h = getHeight();
skipNode *newNode = new skipNode(val,h);
// Need to update nodes forward pointer to point to new node.
skipNode *curNode = head;
for(int i=h-1; i>=0; i--)
{
while(curNode->getForwardLink(i) != tail && curNode->getForwardLink(i)->getData() < val)
{
curNode = curNode->getForwardLink(i);
}
// curNode represents node at level i whose forward[i] = new Node .
// copy newNode.forward[i] = curNode.forward[i]
newNode->setForwardLink(curNode->getForwardLink(i),i);
curNode->setForwardLink(newNode,i);
}
}
// Search value if present return node else return NULL.
skipNode* searchNode(int val)
{
// Start from head Node and search at topMost level.
skipNode *ptr = head;
for(int level = maxHeight-1; level >=0; level--)
{
skipNode *nextNode = ptr->getForwardLink(level);
// Narrow down search from ptr to tail or node having value >= val
while(nextNode->getData() < val && nextNode != tail)
{
ptr = nextNode;
nextNode = nextNode->getForwardLink(level);
}
if(nextNode->getData() == val)
return nextNode;
}
return NULL;
}
void deleteNode(int val)
{
// check if node exist
skipNode *toDelete = searchNode(val);
if(toDelete)
{
// Get height of node to be deleted.
int level = toDelete->getHeight();
// forward pointer of nodes just before delete node neeeds updation of forward pointer.
skipNode *curNode = head;
for(int i=level-1; i>=0; i--)
{
while(curNode->getForwardLink(i) != toDelete)
{
curNode = curNode->getForwardLink(i);
}
curNode->setForwardLink(toDelete->getForwardLink(i),i);
}
}
else
{
return;
}
}
void displaySkipList()
{
for(int level = maxHeight-1; level >=0; level--)
{
cout<<"n";
skipNode* ptr = head;
while(ptr != tail)
{
cout<<" "<<ptr->getData();
ptr = ptr->getForwardLink(level);
}
}
}
};
int skipList::count = 0;
int main()
{
skipList list ;
list.insertNode(10);
list.insertNode(20);
list.insertNode(40);
list.insertNode(50);
list.insertNode(60);
list.insertNode(70);
list.insertNode(30);
list.levelTraversal();
list.deleteNode(40);
cout<<"nnAFTER DELETION";
list.levelTraversal();
system("pause");
}
Friday 14 June 2013
Given an array of n elements, with all elements ranging from 1 to n except one is missing and one is duplicated; find the duplicate and missing element.
/*
ALGORITHM
---------
If we can get the duplicate element, missing elements can be found out by adding all the elements and subtracting from (n(n+1))/2 = sum of 1st n elements.
Add the difference to duplicate element.
1. Scan array from left to right.
Pos =0 ; while pos < N
2. Get value of current element and also its position if the array is in sorted order (desiredPos)
which will be arr[pos]-1 (since array index begins with 0).
a. If element is at its correct position
If desiredPos == arr[pos-1] then move on to next element pos++.
b. Else check value at desiredPos if it is correct then this is a case of duplicate element. Return duplicate value.
Else if (arr[desiredPos] == arr[pos]) return arr[pos]
c. Else swap arr[pos] and arr[desiredPos] and repeat step 2 .
COMPLEXITY
----------
Time : O(n)
Space : O(1)
*/
int getDuplicate(int arr[],int size)
{
int pos = 0;
while(pos <size)
{
int desiredPos = arr[pos]-1;
if(pos == desiredPos)
{
pos++;
}
else if(arr[desiredPos] == arr[pos])
return arr[pos];
else
{
swap(arr,pos,desiredPos);
}
}
return -1;
}
/*
ALTERNATE METHOD
----------------
Let the missing number be x and duplicate element be y.
Sum of all elements = 1+…+n – x + y (y is duplicate and x is missing).
Sum (constant) = (n(n+1))/2 –x + y
Let constant C1 = sum and constant C2 = (n(n+1))/2.
Y – x = C1-C2.
Product of all elements =( 1……n *y )/x
Product = (n! * y )/x
Let constant C3 = product and constant C4 = n!.
C3/C4 = y/x
(C3 * x)/C4 = y.
2 variables and 2 equations, Substitute value of y in 1st equation and solve for x and y.
COMPLEXITY
Time : O(n)
Space : O(1)
*/
Thursday 6 June 2013
Given a number print the next largest number and just smallest number that have same number of 1's in binary representation.
/*
NEXT GREATER NUMBER
-------------------
1. Scan number from right to left bits.
2. As soon as first 1 bit is encountered set the encounterFlag.
3. If encounterFlag is set Turn on the first 0 bit.
4. Turn off the 1 bit on right of above bit.
5. Make this as small as possible to get just next larger number, Push all 1's after this bit to right end.
NEXT SMALLER NUMBER
-------------------
1. Scan number from right to left bits.
2. As soon as first 0 bit is encountered set the encounterFlag.
3. If encounterFlag is set Turn off the first 1 bit.
4. Turn on the 0 bit on right of above bit.
5. Make this as large as possible to get just previous smaller number, Push all 1's after this bit to as much left as possible.
*/
#include <iostream>
using namespace std;
//check if bit at pos is 1 or 0
bool isSet(int number , int pos)
{
if( (number & (1<<pos)) > 0)
return true;
return false;
}
//set Bit at index pos to 1
int setBit(int number , int pos)
{
number |= 1<<pos;
return number;
}
//set bit at index pos to 0
int unsetBit(int number, int pos)
{
number &= ~(1<<pos);
return number;
}
//Return Next Greater number
int getNextGreater(int number)
{
if(number <= 0)
return -1;
int maxIndex;
int countOnes = 0;
int pos = 0;
//Scan number from right to left bit.
for(bool encounterFlag = false; pos < 32 ; pos++)
{
if(encounterFlag)
{
if( !isSet(number , pos) )
{
// set first 0 bit after encounteredFlag is true
number = setBit(number, pos);
// unset 1 bit immediately right of the above bit.
number = unsetBit(number, --pos);
break;
}
else
continue;
}
//As soon as a 1 is encountered, encounteredFlag is set.
if( isSet(number , pos))
encounterFlag = true;
}
//Count no. of 1's after maxIndex.
for(int i=pos -1; i>=0 ; i--)
{
if(isSet(number, i))
countOnes++;
}
//Pushing all 1's to left.
for(int j=pos -1; j>= countOnes; j--)
number = unsetBit(number, j);
for(int k=countOnes-1 ; k>=0; k--)
number = setBit(number, k);
return number;
}
int getNextSmaller(int number)
{
if(number < 0)
return -1;
int maxIndex;
int countOnes = 0;
int pos = 0;
for(bool encounterFlag = false; pos < 32; pos++)
{
if(encounterFlag)
{
if(isSet(number, pos))
{
//After encounterFlag is set Turnoff next 1 Bit.
number = unsetBit(number, pos);
//Turn on 0 bit on right of this bit.
number = setBit(number, --pos);
break;
}
else
continue;
}
//Set encounter flag after first zero is encountered.
if(!isSet(number,pos))
{
encounterFlag = true;
}
}
//Count no. of 1's after maxIndex.
for(int i=pos -1; i>=0 ; i--)
{
if(isSet(number, i))
countOnes++;
}
//Pushing all 1's to left.
for(int j=pos -1; j>= countOnes; j--)
number = setBit(number, j);
for(int k=countOnes-1 ; k>=0; k--)
number = unsetBit(number, k);
return number;
}
int main()
{
cout<<getNextGreater(18)<<endl;
cout<<getNextSmaller(18)<<endl;
system("pause");
}
Subscribe to:
Posts (Atom)