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");
	}
}

[LeetCode #5] LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

public class LRUCache {
	class Node {
		int key;
		int value;
		Node prev;
		Node next;
	}
	
	private int lruCapacity;
	private Map<Integer, Node> lruCache;
	private Node head;
	private Node tail;

	public LRUCache(int capacity) {
		this.lruCapacity = capacity;
		this.lruCache = new HashMap<Integer, Node>();
	}

	public int get(int key) {
		// Existing key
		if (this.lruCache.containsKey(key)) {
			// Move to first place
			Node node = this.lruCache.get(key);
			this.moveFirst(node);
			// Return the value
			return node.value;
		}
		// Not found
		return -1;
	}

	private void add(Node node) {
		// Reset position
		node.next = null;
		node.prev = null;
		// First element
		if (null == this.head) {
			this.head = node;
			this.tail = node;
			return;
		}
		// Existing element
		this.head.prev = node;
		node.next = this.head;
		this.head = node;
	}

	private void remove(Node node) {
		// Nothing to do
		if (this.head == null || null == node) {
			return;
		}
		// The only one item
		if (this.head == this.tail && this.head == node) {
			this.head = null;
			this.tail = null;
			return;
		}
		// Remove from head
		if (node == this.head) {
			this.head.next.prev = null;
			this.head = this.head.next;
			return;
		}
		// Remove from end
		if (node == this.tail) {
			this.tail.prev.next = null;
			this.tail = this.tail.prev;
			return;
		}
		// Remove in the middle
		node.prev.next = node.next;
		node.next.prev = node.prev;

	}

	private void removeLast() {
		this.remove(this.tail);
	}

	private void moveFirst(Node node) {
		this.remove(node);
		this.add(node);
	}

	public void set(int key, int value) {
		if (this.lruCache.containsKey(key)) {
			Node node = this.lruCache.get(key);
			this.moveFirst(node);
			node.value = value;
			return;
		}
		// Out of capacity, cleaning the oldest slot
		if (this.lruCache.size() >= this.lruCapacity) {
			int id = this.tail.key;
			this.removeLast();
			this.lruCache.remove(id);
		}

		// New slot
		Node node = new Node();
		node.key = key;
		node.value = value;
		this.add(node);
		this.lruCache.put(key, node);
	}
}

Google Code Jam Practice Problem – File Fix-it

Problem

On Unix computers, data is stored in directories. There is one root directory, and this might have several directories contained inside of it, each with different names. These directories might have even more directories contained inside of them, and so on.

package avdongre.google.code.jam;

import java.util.HashSet;
import java.util.Scanner;

public class Solution {
	private static void solve(String[] existingDirectories,
			String[] directoriesTobeCreated) {
		HashSet<String> availableDirectories = new HashSet<String>();
		for ( int i = 0; i < existingDirectories.length; i++) {
			String[] splits = existingDirectories[i].split("/");
			StringBuilder sb = new StringBuilder();
			for ( int j = 0; j < splits.length; j++ ) {
				if ( splits[j].length() != 0) {					
					availableDirectories.add(sb.append("/").append(splits[j]).toString());
				} 
			}
			sb.setLength(0);
		}
		int mkdirCount = 0;
		for ( int i = 0; i < directoriesTobeCreated.length; i++) {
			String[] splits = directoriesTobeCreated[i].split("/");
			StringBuilder sb = new StringBuilder();
			for ( int j = 0; j < splits.length; j++ ) {
				if ( splits[j].length() != 0) {
					String possibleNewDirectory = sb.append("/").append(splits[j]).toString();
					if ( availableDirectories.contains(possibleNewDirectory) == false) {						
						availableDirectories.add(possibleNewDirectory);						
						mkdirCount++;
					} else {
					}
				}
			}
			sb.setLength(0);
		}
		System.out.println(mkdirCount);
	}

	public static void main(String[] args) {
		Scanner stdin = new Scanner(System.in);
		// number of test cases
		int T = Integer.parseInt(stdin.nextLine());
		for (int i = 0; i < T; i++) {
			String next = stdin.nextLine();
			String[] next_split = next.split(" ");
			int N = Integer.parseInt(next_split[0]);
			int M = Integer.parseInt(next_split[1]);

			String[] existingDirectories = new String[N];
			for (int j = 0; j < N; j++) {
				existingDirectories[j] = stdin.nextLine();
			}
			String[] directoriesTobeCreated = new String[M];
			for (int k = 0; k < M; k++) {
				directoriesTobeCreated[k] = stdin.nextLine();
			}
			System.out.print("Case #" + ( i + 1) + ": ");
			solve(existingDirectories, directoriesTobeCreated);
		}

	}

}

Google Code Jam Practice Problem – T9 Spelling

Problem

The Latin alphabet contains 26 characters and telephones only have ten digits on the keypad. We would like to make it easier to write a message to your friend using a sequence of keypresses to indicate the desired characters. The letters are mapped onto the digits as shown below. To insert the character B for instance, the program would press 22. In order to insert two characters in sequence from the same key, the user must pause before pressing the key a second time. The space character ‘ ‘ should be printed to indicate a pause. For example, 2 2 indicates AA whereas 22 indicates B.

Old_Phone

package avdongre.google.code.jam;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Solution {
	static Map<Character, String> keyToNumberMap = new HashMap<Character, String>();
	static Map<Character, Integer> keyOnSameButtton = new HashMap<Character, Integer>();

	static {
		keyToNumberMap.put('a', "2");
		keyToNumberMap.put('b', "22");
		keyToNumberMap.put('c', "222");

		keyToNumberMap.put('d', "3");
		keyToNumberMap.put('e', "33");
		keyToNumberMap.put('f', "333");

		keyToNumberMap.put('g', "4");
		keyToNumberMap.put('h', "44");
		keyToNumberMap.put('i', "444");

		keyToNumberMap.put('j', "5");
		keyToNumberMap.put('k', "55");
		keyToNumberMap.put('l', "555");

		keyToNumberMap.put('m', "6");
		keyToNumberMap.put('n', "66");
		keyToNumberMap.put('o', "666");

		keyToNumberMap.put('p', "7");
		keyToNumberMap.put('q', "77");
		keyToNumberMap.put('r', "777");
		keyToNumberMap.put('s', "7777");

		keyToNumberMap.put('t', "8");
		keyToNumberMap.put('u', "88");
		keyToNumberMap.put('v', "888");

		keyToNumberMap.put('w', "9");
		keyToNumberMap.put('x', "99");
		keyToNumberMap.put('y', "999");
		keyToNumberMap.put('z', "9999");

		keyToNumberMap.put(' ', "0");

		keyOnSameButtton.put('a', 1);
		keyOnSameButtton.put('b', 1);
		keyOnSameButtton.put('c', 1);

		keyOnSameButtton.put('d', 2);
		keyOnSameButtton.put('e', 2);
		keyOnSameButtton.put('f', 2);

		keyOnSameButtton.put('g', 3);
		keyOnSameButtton.put('h', 3);
		keyOnSameButtton.put('i', 3);

		keyOnSameButtton.put('j', 4);
		keyOnSameButtton.put('k', 4);
		keyOnSameButtton.put('l', 4);

		keyOnSameButtton.put('m', 5);
		keyOnSameButtton.put('n', 5);
		keyOnSameButtton.put('o', 5);

		keyOnSameButtton.put('p', 6);
		keyOnSameButtton.put('q', 6);
		keyOnSameButtton.put('r', 6);
		keyOnSameButtton.put('s', 6);

		keyOnSameButtton.put('t', 7);
		keyOnSameButtton.put('u', 7);
		keyOnSameButtton.put('v', 7);

		keyOnSameButtton.put('w', 8);
		keyOnSameButtton.put('x', 8);
		keyOnSameButtton.put('y', 8);
		keyOnSameButtton.put('z', 8);

		keyOnSameButtton.put(' ', 9);

	}

	private static String solve(String nextLine) {
		char[] nextLineCharArray = nextLine.toCharArray();
		char previous = nextLineCharArray[0];
		StringBuilder sb = new StringBuilder();
		sb.append(keyToNumberMap.get(previous));
		for (int i = 1; i < nextLineCharArray.length; i++) {
			char current = nextLineCharArray[i];
			if (keyOnSameButtton.get(previous) == keyOnSameButtton.get(current)) {
				sb.append(" ");
			}
			previous = current;
			sb.append(keyToNumberMap.get(previous));
		}
		return sb.toString();
	}

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		// number of test cases
		int N = Integer.parseInt(stdin.nextLine());
		for (int i = 0; i < N; i++) {
			System.out.println("Case #" + (i + 1) + ": "
					+ solve(stdin.nextLine()));
		}
	}

}

Google Code Jam Practice Problem – Store Credit

Problem is described at Store Credit

Analysis
This is variation of the problem where you have you have unsorted array of integers and sum K. You need to find two numbers from the array whose sum is K

package avdongre.google.code.jam;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Solution {
	private static void solve(int credit, int numOfItems, int[] items) {
		// Map has key[i] = item[i]
		// and value[i] = Index of Item in items array + 1
		Map<Integer, Integer> itemToCreditSum = new HashMap<Integer, Integer>();
		for (int i = 0; i < numOfItems; i++) {
			if (itemToCreditSum.get(credit - items[i]) != null) {
				System.out.println(itemToCreditSum.get(credit - items[i]) + " "
						+ (i + 1));
				break;
			} else {
				itemToCreditSum.put(items[i], i + 1);
			}
		}
	}

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		// number of test cases
		int N = Integer.parseInt(stdin.nextLine());
		for (int i = 0; i < N; i++) {
			// Read credit
			int C = Integer.parseInt(stdin.nextLine());
			// Number of Items in the store
			int I = Integer.parseInt(stdin.nextLine());
			// Create item array
			int[] items = new int[I];
			// Read the items values
			String next = stdin.nextLine();
			String[] next_split = next.split(" ");
			for (int j = 0; j < I; j++) {
				int item = Integer.parseInt(next_split[j]);
				items[j] = item;
			}
			System.out.print("Case #" + (i + 1) + ": ");
			solve(C, I, items);
		}
	}

}

[LeetCode #98] Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.

package avdongre.leetcode;

public class Solution {
	java.util.ArrayList<Integer> arr = new java.util.ArrayList<Integer>();

	private void performInorder(TreeNode root) {
		if ( root == null) {
			return;
		}
		performInorder(root.left);
		arr.add(root.val);
		performInorder(root.right);
	}

	public boolean isValidBST(TreeNode root) {
		if (root == null) {
			return true;
		}
		performInorder(root);
		int previous = arr.get(0).intValue();
		
		for (int i = 1 ; i < arr.size();i++) {
			int current = arr.get(i).intValue(); 
			if (current <= previous) {
				return false;
			}
			previous = current;
		}
		return true;
	}

	public static void main(String[] args) {
		Solution s = new Solution();
		{
			TreeNode tn1 = new TreeNode(1);
			TreeNode tn2 = new TreeNode(1);
			tn1.left = tn2;
			System.out.println(s.isValidBST(tn1));
		}		
		
		{
			TreeNode tn5  = new TreeNode(5);
			TreeNode tn14 = new TreeNode(14);
			TreeNode tn1  = new TreeNode(1);
			
			tn5.left = tn14;
			tn14.left = tn1;
			
			System.out.println(s.isValidBST(tn5));
		}		
		
		{
			System.out.println(s.isValidBST(null));
		}
		
	}

}

Programming Pearls Chapter 1 Problem 6

What would you recommend to the programmer if, instead of saying that each integer could appear at most once, he told you that each integer could appear at most ten times? How would your solution change as a function of the amount of available storage?

package avdongre.programming.pearls;

/**
 * Programming Pearls Chapter 1 Problem 6 
 * 
 * 6. What would you recommend to the  programmer if, instead of saying that 
 * each integer could appear at most once, he told you that each integer 
 * could appear at most ten times? How would your solution change as a 
 * function of the amount of available storage?
 * 
 * @author adongre
 *
 */

public class SolutionChapterOneProblemSix {

	public void solve(int range, int repetition, int[] array) {
		/*
		 * Since each number can appear at most 'repetition' times Let us have bit-vector
		 * with size equal to range * 10
		 */
		java.util.BitSet storage = new java.util.BitSet(range * repetition);
		for (int i = 0; i < array.length; i++) {
			/*
			 * Find the slot where the new number should be stored in the form
			 * of bit ON or OFF
			 */
			int currentNumber = array[i];
			/* Identify the slot start */
			int slotStart = (currentNumber * range) - range;
			/* iterate over the slot */
			int slotEnds = slotStart + repetition - 1;
			for (int j = slotStart; j < slotEnds; j++) {
				if ( storage.get(j) == false) {
					storage.set(j);
					break;
				}
			}

		}
		for ( int i = 0; i < storage.length(); i++) {
			if ( storage.get(i)) {
				System.out.println((i / range) + 1);
			}
		}
	}

	public static void main(String[] args) {
		SolutionChapterOneProblemSix sol = new SolutionChapterOneProblemSix();
		{
			int [] array = new int [] {1,2,3,4,5,1,2,3,4,5,1,2,3,4,5};		 
			sol.solve(5, 5, array);
		}
	}

}

The Algorithm Design Manual Chapter 4 Problem 34

Suppose that you are given a sorted sequence of distinct integers {a1 , a2 , . . . , an },
drawn from 1 to m where n < m. Give an O(lg n) algorithm to find an integer ≤ m that is not present in a. For full credit, find the smallest such integer.

package avdongre.tadm;

public class SmallestMissingNumber {
	public int findSmallestMissingNumber(int[] arr) {

		int low = 0;
		int high = arr.length - 1;
		while (low <= high) {
			int mid = (low + high) / 2;
			if (arr[mid] > mid + 1) {
				high = mid - 1;
			} else if (arr[mid] <= mid + 1) {
				low = mid + 1;
			}
		}
		return low + 1;
	}

	public static void main(String[] args) {
		SmallestMissingNumber smn = new SmallestMissingNumber();
		{
			int[] arr = new int[] { 1, 2, 4, 5 };
			System.out.println(smn.findSmallestMissingNumber(arr));
		}

	}

}

Follow

Get every new post delivered to your Inbox.