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?