Problem:
Generate all the strings of n bits.
Solution:
Subtract and Conquer.
Complexity: O(2^n)
Code:
Generate all the strings of n bits.
Solution:
Subtract and Conquer.
Complexity: O(2^n)
Code:
Popular Posts
-
Problem: Imagine a robot sitting on the upper left hand corner of an NxN grid. The robot can only move in two directions: right and down. ... -
Problem: Insertion sort can be expressed as a recursive procedure as follows. In order to sort A[1 n], we recursively sort A[1 n -1] ...
-
Problem: Write an efficient program for printing k largest elements in an array. Elements in array can be in any order. For example, if...
-
Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Print all the keys of tree in range k1 to k2. i.... -
How many comparisons are necessary to determine the minimum of a set of n elements? n-1 comparisions. It is not difficult to devise an ...
-
Problem: Describe a Θ(n lg n)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exi...
-
Problem: Given a Singly Linked List, starting from the second node delete all alternate nodes of it. For example, if the given linked lis...
-
Given a Binary Tree and a key, write a function that prints all the ancestors of the key in the given binary tree. For example, if the give...
-
Problem: Although merge sort runs in Θ(n lg n) worst-case time and insertion sort runs in Θ(n2) worstcase time, the constant factors in i...
-
Problem: Describe an implementation of the procedure RANDOM(a, b) that only makes calls to RANDOM(0, 1). What is the expected running tim...
Monday, September 12, 2011
Tuesday, August 30, 2011
Sunday, August 28, 2011
a1a2a3....anb1b2b3....bn to a1b1a2b2a3b3....anbn
Problem:
Convert a1a2a3....anb1b2b3.....bn to
a1b1a2b2a3b3.....anbn
in O(n) time and O(1) space
Solution:
Complexity: O(n) time O(1) space
Code:
Convert a1a2a3....anb1b2b3.....bn to
a1b1a2b2a3b3.....anbn
in O(n) time and O(1) space
Solution:
[b] a b c d e 1 2 3 4 5 [2<=5, index=2*2-1=3]
[c] a b b d e 1 2 3 4 5 [3<=5, index=3*2-1=5]
[e] a b b d c 1 2 3 4 5 [5<=5, index=5*2-1=9]
[4] a b b d c 1 2 3 e 5 [9>5, index=(9-5)*2=8]
[3] a b b d c 1 2 4 e 5 [8>5, index=(8-5)*2=6]
[1] a b b d c 3 2 4 e 5 [6>5, index=(6-5)*2=2]
[b] a 1 b d c 3 2 4 e 5 [startindex=index=2]
[d] a 1 b d c 3 2 4 e 5 [4<=5,index=4*2-1=7]
[2] a 1 b d c 3 d 4 e 5 [7>5,index=(7-5)*2=4]
[d] a 1 b 2 c 3 d 4 e 5 [startindex=index=4]
Complexity: O(n) time O(1) space
Code:
Subscribe to:
Posts (Atom)