Morgan Stanley Interview Question
Sales Development RepresentativesCountry: India
i guess the complexity should be O(logn) for printing each number. It can't be less than that
We can take advantage of inbuilt function of Integer class to get binary output
public void printBinary(int num) {
for (int i = 1; i <= num ; i++) {
System.out.println(Integer.toBinaryString(num));
}
}
public static void printBinary(int n) {
for (int i = 1; i <= n; i++) {
doPrintBinary(i);
System.out.println();
}
}
public static void doPrintBinary(int n) {
if (n > 1) {
doPrintBinary(n >> 1);
}
System.out.print(n & 1);
}
// how does it look like? Constant time. It could be improved by not using a temporary buffer
char* print_binary(int x){
int mask = 1;
int counter = 0;
char temp[32];
int last = -1;
while (counter < 32) {
if ((mask & x) != 0){
temp[counter] = '1';
last = counter;
}
else {
temp[counter] = '0';
}
mask <<= 1;
counter++;
}
char* output = new char[last+2];
for(int i=last;i>=0;i--){
output[last-i] = temp[i];
}
output[last+1] = '\0';
return output;
}
//You just call it n times:
for (int i=1;i<=n;i++){
std::cout << print_binary(i);
if (i<n)
std::cout << " ";
}
You actually need to call it 2^n times. From my understanding n is the number of digits not the upper bound.
I assume this is what is being asked ?
static void Main(string[] args)
{
// Given a number n write a program to print all binary numbers starting from 1. For example n=6, print 1, 10, 11, 100, 101, 110
// Consequent numbers 111, 1000, 1001 1010
string str = "1";
int n = 100;
int nextPosToSearch = 0;
for (int i = 1; i <= n; i++)
{
Console.WriteLine(str);
char[] digits = str.ToCharArray();
for(int j = nextPosToSearch; j >=0; j--)
{
if (digits[j] == '1')
{
if (j == 0)
{
digits = new char[digits.Length + 1];
digits[0] = '1';
for (int k = 1; k < digits.Length; k++)
digits[k] = '0';
nextPosToSearch = digits.Length-1;
}
else
{
digits[j] = '0';
nextPosToSearch = j;
}
}
else
{
digits[j] = '1';
nextPosToSearch = j - 1;
break;
}
}
str = new string(digits);
}
Console.Read();
}
#include<stdio.h>
#include<stdlib.h>
void binary(long n)
{
int tic = 0;
for (long i = 1 << 30; i > 0; i = i / 2)
{
if ((n & i))
{
printf("1");
tic = 1;
}
else
{
if (tic == 1)
printf("0");
}
}
printf("\n");
}
int main()
{
long n;
scanf("%d", &n);
for (long i = 1; i <= n; i++)
binary(i);
system("pause");
return 0;
}
public static String recursive(int n){
if(n > 0){
if((n & 1) == 1){
return recursive(n >> 1) + "1";
}else{
return recursive(n>>1) + "0";
}
}
return "";
}
public static void main(String[] args) {
int num = 0;
try {
num = System.in.read();
num -= 48;
for(int i = 1; i <= num; i++){
System.out.println(recursive(i));
}
} catch (IOException e) {
e.printStackTrace();
}
}
This should work in amortized O(1). The logic is simple, I manually keep on incrementing the number in binary form starting from 1. The operations simulate binary addition. There is no number to binary conversion done.
Code:
public class BinaryStringUptoN {
public static void printN(int n){
StringBuilder sb = new java.lang.StringBuilder("1");
System.out.println(sb);
for (int i = 1; i < n; i++) {
System.out.println(incrementBin(sb, sb.length()));
}
// System.out.println(incrementBin(new StringBuilder("11011"), 5));
}
public static String incrementBin(StringBuilder i, int lookAt){
int n = lookAt;
if(i.charAt(n-1)=='0'){
i.replace(n-1, n, "1");
}else if(i.charAt(n-1)=='1' && n==1){
i.replace(n-1, n, "0");
i.insert(0, 1);
}else{
i.replace(n-1, n, "0");
if(n>1 && i.charAt(n-2)=='1'){
n--;
incrementBin(i, n);
}else if(n>1){
incrementBin(i, n-1);
}
}
return i.toString();
}
public static void main(String[] args) {
printN(5);
}
}
#include <iostream>
#include <string>
#include <cstdlib>
#include <cmath>
#include <ctype.h>
#include <string.h>
#include <queue>
using namespace std;
void generate(int n)
{
queue<string> q;
q.push("1");
int i = 1;
while (i++ <= n)
{
q.push(q.front () + "0");
q.push(q.front () + "1");
cout<< q.front() <<' ';
q.pop();
}
}
int main()
{
int n = 2 ;
generate(n);
return 0;
}
public class DecimalToBinary {
public static void main(String[] args) {
int N = 12;
for(int i = 0; i<=N; i++) {
if(i == 0 || i ==1)
System.out.println(i);
else {
decimalToBinary(i);
System.out.println();
}
}
}
public static void decimalToBinary (int num) {
if(num == 0 || num ==1) {
System.out.print(num);
return;
}
decimalToBinary(num / 2);
System.out.print(num % 2);
}
}
1)use a queue and enqueue 1 in it and intialize a counter as 0.
- vishal July 18, 20142)do this step while q is not empty and counter<n
2.a)dequeue the front element and print it.
2.b)append 0 and 1 to the popped element and enqueue it back to the queue.
finally all the element will be printed in binary in o(1)...