Ohh !!! and I thought do…while(0) is just useless

Over the period of years, I saw following kind of code in many places

#define FOO(X) do { f(X); g(X); } while (0)

But this is not useless but a clear trick to avoid unwanted Empty Expression

Consider you have defined the same macro as follows

#define BAR(X) f(x); g(x)

and you are using the same as follows in your main code

if (corge)
  BAR(corge);
else
  gralt();

Above code would be expanded as follows

if (corge)
  f(corge); g(corge);
else
  gralt();

This would cause compiler to cry from bottom of its neck. This is not what you wanted, and this is where do…while(0) trick comes as a savior.

Smallest Zero One Number of multiples of n

ZeroOne is the number, whose digits are either 0 or 1. You have given a number n and need to find the smallest multiplier which is ZeroOne Number

For example for 4 smallest possible ZeroOne Multipler is 100

Solution

I have tried to solve this but really could not find the optimize solution.

#include <stdio.h>
int getZeroOneMultipler(int number) {
  long multiplier = 1;
  while(1) {
    long product = multiplier++ * number;
    long temp = product;
    while ( temp != 0 ) {
      int digit = temp % 10;
      if ( digit != 0 && digit != 1 ) {
        break;
      }
      temp /= 10;
    }
    if ( temp == 0 ) {
      return product;
    }
  }
}

int main(int argc, char** argv) {
  int i = 0;
  for ( i = 0; i < 100; i++) {
      printf("%d = %d\n", i, getZeroOneMultipler(i));
  }
  return 0;
}

British computer magazine had a programming contest [ Updated ]

Friend ( Rishitesh Mishra ) suggested to increment counter by 9, as he believe that 9 is magic number and to my surprise I could get the result in less than a second.

package avdongre.bcm.puzzle;

import java.util.Arrays;

public class Solution {
	public static void main(String[] args) {
		long start = java.util.Calendar.getInstance().getTimeInMillis();
		int[] set = new int[10];
		int counter = 0;
		boolean solutionFound = false;
		for (int i = 123456789; i < 987654321; i = i + 9) {
			if (solutionFound) {
				break;
			}
			Arrays.fill(set, 0);
			int temp = i;
			boolean validNumber = true;
			while (temp != 0) {
				int digit = temp % 10;
				if (digit == 0) {
					validNumber = false;
					break;
				}
				if (set[digit] == 0) {
					set[digit] = 1;
				} else {
					validNumber = false;
					break;
				}
				temp /= 10;
			}
			if (validNumber) {
				counter++;
				if (counter == 100000) {
					System.out.println(i);
					solutionFound = true;
				}
			}
		}
		long end = java.util.Calendar.getInstance().getTimeInMillis();
		System.out.println("it took this long to complete this stuff: "
				+ ((end - start) * 0.001) + " seconds");
	}
}

British computer magazine had a programming contest

Objective

25 years ago, a British computer magazine had a programming contest and this was one of the puzzles.
There are a large number of 9 digit integers in the range 123456789 to 987654321 where each digit only appears once. What is the 100,000th number in this sequence?

Example

The first number is 123456789, the second is 123456798, the third is 123456879 and so on. No digit can repeat so 122345675 is not a valid number in this sequence.
The problem was “Write a program that outputs the 100,000th number as fast as possible. Use any algorithm, except you cannot pre-calculate the answer and then write a program that just prints the result. Your entry must calculate the number!”. This ran through June 2007

Approach
I am sure this has something to do with permutation, but I could not figure out the same. I went ahead with simple brute-force approach.

1. Iterate over the range 123456789 to 987654321
2. Get all the digits of the number
3. Store each digit into a set and check for uniqueness
4. If the digit is 0 ignore that number
5. If the digit is repeated ignore that number.

Here is my first Java version

package avdongre.bcm.puzzle;

import java.util.HashSet;
import java.util.Set;

public class Solution {
	public static void main(String[] args) {
		long start = java.util.Calendar.getInstance().getTimeInMillis();
		Set<Character> uniqueCheckSet = new HashSet<Character>();
		int counter = 0;
		boolean solutionFound = false;
		for (int i = 123456789; i < 987654321; i++) {
			if ( solutionFound ) {
				break;
			}
			char[] digits = String.valueOf(i).toCharArray();
			boolean validNumber = true;
			for (int j = 0; j < digits.length; j++) {
				if (digits[j] == '0') {
					validNumber = false;
					break;
				}
				if ( false == uniqueCheckSet.add(digits[j])) {
					validNumber = false;
					break;
				}
				
			}
			if (validNumber) {
				counter++;
				if ( counter == 100000) {
					System.out.println(i);		
					solutionFound = true;
				}
			}
			uniqueCheckSet.clear();
		}
		long end = java.util.Calendar.getInstance().getTimeInMillis();
		System.out.println("it took this long to complete this stuff: " + ((end - start) * 0.001) + " seconds");
	}
}

This code took around 35 seconds to finish.

My friend force me to try the same for C++, but we come up with new approach of not using set but simple array in which if the digit is already seen the just set the value to 1 and continue.
With Optimization flag on following C++ code took around 3 seconds to finish

#include <iostream>
#include <vector>
using namespace std;
int main(int argc, char ** argv) {
  int counter = 0;
  bool solutionFound = false;
  std::vector<int> set(10);  
  for (int i = 123456789; i < 987654321; ++i) {
    if ( solutionFound ) {
      break;
    }
    int temp = i;
    bool validNumber = true;    
    std::fill(set.begin(), set.end(), 0);    
    while (temp)
    {
      int digit = temp % 10;
      if (digit == 0) {
        validNumber = false;
        break;
      } 
      if ( set[digit] == 0 ) {
         set[digit] = 1;
      } else {
        validNumber = false;
        break;
      }
      temp /= 10;
    }        
    if (validNumber) {
      counter++;
      if ( counter == 100000) {
        cout << i << endl;
        solutionFound = true;
      }
    }
  }
}

Done the same with java and it has dramatically improved performance to 5 seconds

package avdongre.bcm.puzzle;

import java.util.Arrays;

public class Solution {
	public static void main(String[] args) {
		long start = java.util.Calendar.getInstance().getTimeInMillis();
		int[] set = new int[10];
		int counter = 0;
		boolean solutionFound = false;
		for (int i = 123456789; i < 987654321; i++) {
			if (solutionFound) {
				break;
			}
			Arrays.fill(set, 0);
			int temp = i;
			boolean validNumber = true;
			while (temp != 0) {
				int digit = temp % 10;
				if (digit == 0) {
					validNumber = false;
					break;
				}
				if (set[digit] == 0) {
					set[digit] = 1;
				} else {
					validNumber = false;
					break;
				}
				temp /= 10;
			}
			if (validNumber) {
				counter++;
				if (counter == 100000) {
					System.out.println(i);
					solutionFound = true;
				}
			}
		}
		long end = java.util.Calendar.getInstance().getTimeInMillis();
		System.out.println("it took this long to complete this stuff: "
				+ ((end - start) * 0.001) + " seconds");
	}
}