Sunday, September 28, 2014

number system with only 3 and 4

Reference :-
http://www.geeksforgeeks.org/zoho-interview-set-2-campus/

Problem statement:-
Form a number system with only 3 and 4. Find the nth number of the number system.
Eg.) The numbers are: 3, 4, 33, 34, 43, 44, 333, 334, 343, 344, 433, 434, 443, 444, 3333, 3334, 3343, 3344, 3433, 3434, 3443, 3444 ….

My approach.
3 & 4 are starting numbers.
Prefixing them with 3 gives next numbers viz. 33, 34
Similarly prefixing then gives next numbers viz. 43,44.

So now list is 3,4,33,34,43,44.

We have already considered 3 & 4. If we repeat the process for remaining numbers  i.e. 33,34,43,44.
viz. Prefixing them with 3 gives next numbers viz. 333, 334, 343, 344
viz. Prefixing them with 4 gives next numbers viz. 433, 434, 443, 444

So now list is 3,4,33,34,43,44,333, 334, 343, 344,433, 434, 443, 444

Code :-
Also shared at
http://ideone.com/nkuJkT


import java.util.ArrayList;
public class CombinationOf3And4 {

/*
 * http://www.geeksforgeeks.org/zoho-interview-set-2-campus/
 * Form a number system with only 3 and 4. Find the nth number of the number system.
 * e.g. The numbers are: 3, 4, 33, 34, 43, 44, 333, 334, 343, 344, 433, 434, 443, 444, 3333, 3334, 3343, 3344, 3433, 3434, 3443, 3444 ….
 */
public static void main(String[] args) {
printCombinations(20);
}
public static void printCombinations(int n){
ArrayList<String> numbers = new ArrayList<String> ();
numbers.add("3");
numbers.add("4");
int currentNumber = 0;
while(numbers.size()<n){
ArrayList<String> threePrefixed = new ArrayList<String>();
ArrayList<String> fourPrefixed = new ArrayList<String>();

for(int i=currentNumber;i<numbers.size();i++){
// Retrieve all numbers.
// For every number create new number with prefix "3"  & with prefix "4".
// then push all 3-prefixed-number into array and then 4-prefixed-number 
threePrefixed.add("3"+numbers.get(i));
fourPrefixed.add("4"+numbers.get(i));
currentNumber++;
}

for(String s:threePrefixed){
numbers.add(s);
}
for(String s:fourPrefixed){
numbers.add(s);
}
}
System.out.println("Printing result");
for(String s:numbers){
System.out.print(" "+s);
}

}
}



No comments:

Post a Comment