Prove the following

Consider the following criteria for integers:
- The digits in the number are sorted(ascending order, left to right)
- The digits in the square of the number are also sorted
(Ex: N=12 N^2 = 144 fits the bill, but N=11, N^2 = 121 - does not. )

Prove that the number of numbers that satisfy this criteria is infinite.
(Got it from Knuth's lectures on the Stanford site.)

Compare two n-bit numbers using CNF

Here is an interesting problem:

Given two n-bit numbers A and B, represented as two single-bit-arrays A_n-1...A₀ and B_n-1...B₀,
Write a program that generates a CNF (Conjunctive Normal Form) expression that checks if A is less than B.

Hint - The CNF expression for checking if a single-bit number A₀ is less than another single-bit number B₀ is = !A₀.B₀ = !(A₀ + !B_O) in CNF

I'll post the answer to this soon.

Can you sort in O(n) time?

One of the questions programmers ask if it is possible to sort in O(n) time? Is it possible? Hint: What if we had all numbers as unique (no repetition of numbers in the input)?

We'll it's certainly possible, but it can be expensive. Consider random numbers with maximum value say 100, let's say we have the sequence

92 51 11 69 24 35 17 36 26 98

The program to sort this sequence in O(n) is time is given at code for O(n) sorting

The output of the program is

11 17 24 26 35 36 51 69 92 98

Question 1: What are the disadvantages of such sorting methods - give at-least two
Question 2: Can you write code, given a sequence of numbers as input, it can verify if the array is in sorted order

PS: The curious and smart will notice that O(n) is not the correct analysis of the algorithm, so whats the correct complexity then?

Hat Throwing Problem

I am working on an interesting problem in probability. Since, I found the problem hard to solve analytically, I am trying to visualize the solution.

The problem is taken from Sheldon M Ross's Introduction to Probability Models (seventh Edition). Problem number 32, page 19 is stated as

Suppose all 'n' men at a party throw their hats in the center of the room. Each man randomly selects a hat. Show that the probability that none of the n men, selects his own hat is

I've written a computer program to actually calculate the probability from the given sample space. The source code is at "The Hat Throwing Problem Code"

I have the analytical solution, but I want to hide it, till you solve it for yourself.

Welcome

This blog has been created out of our desire to learn and share our experience in computing. We hope to keep you interested and coming in on a regular basis with interesting problems, puzzles, solutions and trivia.

The blog will over a period of time evolve in a self aligned and organized group of topics. We hope the pattern will become clearer as the topics progress.

So, welcome and please keep us updated. The success of this blog will largely depend on regular feedback and help from all of you.