Decimal to Binary using Stacks | Data Structure MCQs

1.

Express -15 as a 6-bit signed binary number.

A.) 001111
B.) 101111
C.) 101110
D.) 001110

The first 4 1s from the right represent the number 15, 2 more bits are padded to make it 6 digits and the leftmost bit is a 1 to represent that it is -15.

2.

Which of the following code snippet is used to convert decimal to binary numbers?

A.)
```public void convertBinary(int num)
{
int bin[] = new int[50];
int index = 0;
while(num > 0)
{
bin[index++] = num/2;
num = num%2;
}
for(int i = index-1;i >= 0;i--)
{
System.out.print(bin[i]);
}
}```
B.)
```public void convertBinary(int num)
{
int bin[] = new int[50];
int index = 0;
while(num > 0)
{
bin[index++] = num%2;
num = num/2;
}
for(int i = index-1;i >= 0;i--)
{
System.out.print(bin[i]);
}
}```
C.)
```public void convertBinary(int num)
{
int bin[] = new int[50];
int index = 0;
while(num > 0)
{
bin[++index] = num%2;
num = num/2;
}
for(int i = index-1;i >= 0;i--)
{
System.out.print(bin[i]);
}
}```
D.)
```public void convertBinary(int num)
{
int bin[] = new int[50];
int index = 0;
while(num > 0)
{
bin[++index] = num/2;
num = num%2;
}
for(int i = index-1;i >= 0;i--)
{
System.out.print(bin[i]);
}
}```

Take the modulus by 2 of the number and store in an array while halving the number during each iteration and then display the contents of the array.

3.

Which is the predefined method available in Java to convert decimal to binary numbers?

A.) toBinaryInteger(int)
B.) toBinaryValue(int)
C.) toBinaryNumber(int)
D.) toBinaryString(int)

The method toBinaryString() takes an integer argument and is defined in java.lang package. Usage is java.lang.Integer.toBinaryString(int) this returns the string representation of the unsigned integer value.

4.

Using stacks, how to obtain the binary representation of the number?

A.)
```public void convertBinary(int num)
{
Stack<Integer> stack = new Stack<Integer>();
while (num != 0)
{
int digit = num / 2;
stack.push(digit);
num = num % 2;
}
System.out.print("
Binary representation is:");
while (!(stack.isEmpty() ))
{
System.out.print(stack.pop());
}
}```
B.)
```public void convertBinary(int num)
{
Stack<Integer> stack = new Stack<Integer>();
while (num != 0)
{
int digit = num % 2;
stack.push(digit);
}
System.out.print("
Binary representation is:");
while (!(stack.isEmpty() ))
{
System.out.print(stack.pop());
}
}```
C.)
```public void convertBinary(int num)
{
Stack<Integer> stack = new Stack<Integer>();
while (num != 0)
{
int digit = num % 2;
stack.push(digit);
num = num / 2;
}
System.out.print("
Binary representation is:");
while (!(stack.isEmpty() ))
{
System.out.print(stack.pop());
}
}```
D.) None of these

Here instead of adding the digits to an array, you push it into a stack and while printing, pop it from the stack.

5.

What is the time complexity for converting decimal to binary numbers?

A.) O(1)
B.) O(n)
C.) O(logn)
D.) O(nlogn)

Since each time you are halving the number, it can be related to that of a binary search algorithm, hence the complexity is O(logn).

6.

Write a piece of code which returns true if the string contains balanced parenthesis, false otherwise.

A.)
```public boolean isBalanced(String exp)
{
int len = exp.length();
Stack<Integer> stk = new Stack<Integer>();
for(int i = 0; i < len; i++)
{
char ch = exp.charAt(i);
if (ch == '(')
stk.push(i);
else if (ch == ')')
{
if(stk.peek() == null)
{
return false;
}
stk.pop();
}
}
return true;
}```
B.)
```public boolean isBalanced(String exp)
{
int len = exp.length();
Stack<Integer> stk = new Stack<Integer>();
for(int i = 0; i < len; i++)
{
char ch = exp.charAt(i);
if (ch == '(')
stk.push(i);
else if (ch == ')')
{
if(stk.peek() != null)
{
return true;
}
stk.pop();
}
}
return false;
}```
C.)
```public boolean isBalanced(String exp)
{
int len = exp.length();
Stack<Integer> stk = new Stack<Integer>();
for(int i = 0; i < len; i++)
{
char ch = exp.charAt(i);
if (ch == ')')
stk.push(i);
else if (ch == '(')
{
if(stk.peek() == null)
{
return false;
}
stk.pop();
}
}
return true;
}```
D.)
```public boolean isBalanced(String exp)
{
int len = exp.length();
Stack<Integer> stk = new Stack<Integer>();
for(int i = 0; i < len; i++)
{
char ch = exp.charAt(i);
if (ch == '(')
stk.push(i);
else if (ch == ')')
{
if(stk.peek() != null)
{
return false;
}
stk.pop();
}
}
return true;
}```

Whenever a ‘(‘ is encountered, push it into the stack, and when a ‘)’ is encountered check the top of the stack to see if there is a matching ‘(‘, if not return false, continue this till the entire string is processed and then return true.

7.

What is the time complexity of the above code?

A.) O(logn)
B.) O(n)
C.) O(1)
D.) O(nlogn)

All the characters in the string have to be processed, hence the complexity is O(n).

8.

For every matching parenthesis, print their indices.

A.)
```public void dispIndex(String exp)
{
Stack<Integer> stk = new Stack<Integer>();
for (int i = 0; i < len; i++)
{
char ch = exp.charAt(i);
if (ch == '(')
stk.push(i);
else if (ch == ')')
{
try
{
int p = stk.pop() + 1;
System.out.println("')' at index "+(i+1)+" matched with ')' at index "+p);
}
catch(Exception e)
{
System.out.println("')' at index "+(i+1)+" is unmatched");
}
}
}
while (!stk.isEmpty() )
System.out.println("'(' at index "+(stk.pop() +1)+" is unmatched");
}```
B.)
```public void dispIndex(String exp)
{
Stack<Integer> stk = new Stack<Integer>();
for (int i = 0; i < len; i++)
{
char ch = exp.charAt(i);
if (ch == '(')
stk.push(i);
else if (ch == ')')
{
try
{
int p = stk.pop() + 1;
System.out.println("')' at index "+(i)+" matched with ')' at index "+p);
}
catch(Exception e)
{
System.out.println("')' at index "+(i)+" is unmatched");
}
}
}
while (!stk.isEmpty() )
System.out.println("'(' at index "+(stk.pop() +1)+" is unmatched");
}```
C.)
```public void dispIndex(String exp)
{
Stack<Integer> stk = new Stack<Integer>();
for (int i = 0; i < len; i++)
{
char ch = exp.charAt(i);
if (ch == ')')
stk.push(i);
else if (ch == '(')
{
try
{
int p = stk.pop() + 1;
System.out.println("')' at index "+(i+1)+" matched with ')' at index "+p);
}
catch(Exception e)
{
System.out.println("')' at index "+(i+1)+" is unmatched");
}
}
}
while (!stk.isEmpty() )
System.out.println("'(' at index "+(stk.pop() +1)+" is unmatched");
}```
D.) None of these