Interview Question
Country: United States
public class TwosCompliment {
public static void main(String[] args) {
TwoC c = new TwoC();
System.out.println(c.twosCompliment("001"));
}
private static class TwoC {
public String twosCompliment(String str) {
if(str == null || str.isEmpty()){
return str;
}
char[] invertedArr = invert(str).toCharArray();
for(int i = invertedArr.length - 1; i >= 0; i--) {
Result result = add(invertedArr[i], '1');
invertedArr[i] = result.result();
if(!result.isCarry()) {
break;
}
}
return new String(invertedArr);
}
private static String invert(String str) {
if(str == null) {
throw new RuntimeException("Test String cannot be empty");
}
char[] strArray = str.toCharArray();
for(int i = 0; i < str.length(); i++) {
if(strArray[i] == '1') {
strArray[i] = '0';
} else {
strArray[i] = '1';
}
}
return new String(strArray);
}
private Result add(char one, char two) {
if(one == '1' && two == '1') {
return new Result(true, '0');
} else if((one == '1' && two == '0') || (one == '0' && two =='1')) {
return new Result(false, '1');
} else {
return new Result(false, '0');
}
}
}
private static class Result {
private boolean isCarry;
private char result;
Result(boolean isCarry, char result) {
this.isCarry = isCarry;
this.result = result;
}
public boolean isCarry() {
return isCarry;
}
public char result() {
return result;
}
}
}
string answer(string s) {
bool flg = 0; // this determines if the first 1 from right is found.
for(int i = s.size() - 1; i >= 0; --i) {
if(flg) s[i] = s[i] == '0' ? '1' : '0';
else flg = s[i] == '1';
}
for(int i = 0; i < (s.size() / 2); ++i) {
swap(s[i], s[s.size() - i - 1]);
}
return s;
}
void swap(char &a, char &b) {
char tmp = a;
a = b;
b = tmp;
}
public class StringOperations(){
public static void main(String[] args){
String inverseString = "111000110";
char[] array = inverseString.toCharArray();
system.out.println(String.valueOf(inverseArray(array));
system.out.println(String.valueOf(getComplement(array));
}
private static char[] inverseArray(char[] array){
//* Method 1 *//
return Collections.inverse(array);
//* Method 2 *//
char[] inverseArray;
for(int i=array.length;i>=0;i--)
{
inverseArray.add(char[i])
}
return inverseArray;
}
public getComplement(char[] array){
for(int i=array.length;i>=0;i--)
{
if(array[i]==0)
{
array[i] = 1;
}
else{
array[i]=0;
}
}
return array;
}
}
import java.io.*;
class StringComplement
{
static String str;
public static void main(String args[]) throws Exception
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
str = br.readLine();
String complementStr = complement(str);
System.out.println("Original String :"+str);
System.out.println("Complemented String :"+complementStr);
}
static String complement(String str)
{
// Take example : 100110
// 1 is replace with only for future reference to 1
String str1 = str.replaceAll("1","2"); //changing all 1's to 2 200220
String str2 = str1.replaceAll("0","1"); //changing all 0's to 1 211221
String str3 = str2.replaceAll("2","0"); // changing all 2's to 0 011001 //final string
return str3;
}
}
import java.io.*;
class StringComplement
{
static String str;
public static void main(String args[]) throws Exception
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
str = br.readLine();
String complementStr = complement(str);
System.out.println("Original String :"+str);
System.out.println("Complemented String :"+complementStr);
}
static String complement(String str)
{
// Take example : 100110
// 1 is replace with only for future reference to 1
String str1 = str.replaceAll("1","2"); //changing all 1's to 2 200220
String str2 = str1.replaceAll("0","1"); //changing all 0's to 1 211221
String str3 = str2.replaceAll("2","0"); // changing all 2's to 0 011001 //final string
return str3;
}
}
#include <stdio.h>
#include<string.h>
char* mystr(char str[])
{
char temp[100];
int i,j;
for (i=strlen(str)-1,j=0;i>=0;i--,j++)
{
temp[j]=str[i];
}
printf("reverse = %s",temp);
for(i=0;i<strlen(str);i++)
{
if(str[i]=='1')
str[i]='0';
else
str[i]='1';
}
printf("1s_com= %s",str);
printf("\n");
if (str[strlen(str)-1]=='0')
str[strlen(str)-1]=str[strlen(str)-1]+1;
return str;
}
int main(void) {
// int i,j,data=5,bitpos,a,b;
char str[]="0011001";
printf("data=%s",str);
printf("2s_com=%s",mystr(str));
return 0;
}
#include <stdio.h>
#include<string.h>
char* mystr(char str[])
{
char temp[100];
int i,j;
for (i=strlen(str)-1,j=0;i>=0;i--,j++)
{
temp[j]=str[i];
}
printf("reverse = %s",temp);
for(i=0;i<strlen(str);i++)
{
if(str[i]=='1')
str[i]='0';
else
str[i]='1';
}
printf("1s_com= %s",str);
printf("\n");
if (str[strlen(str)-1]=='0')
str[strlen(str)-1]=str[strlen(str)-1]+1;
return str;
}
int main(void) {
// int i,j,data=5,bitpos,a,b;
char str[]="0011001";
printf("data=%s",str);
printf("2s_com=%s",mystr(str));
return 0;
}
{{
String twoComplements(String str) {
if(str == null || str.length() == 0)
return str;
StringBuilder strBuf = new StringBuilder();
for (int index = 0; index < str.length(); index++) {
if(str.charAt(index)== '0') {
strBuf.append('1');
}
else
strBuf.append('0');
}
int index = 0;
for (index = str.length() - 1; index >=0 ; index--) {
if(strBuf.charAt(index)== '0') {
strBuf.setCharAt(index,'1');
break;
}
else
strBuf.setCharAt(index,'0');
}
if(index < 0) {
strBuf.insert(0,'1');
}
return strBuf.toString();
}
}}
Code in Java
Time : O(n) , n=length of string
Space : O(1)
private static void twosComplement(String input){
char[] chars=input.toCharArray();
int consecutiveOnesCount=0;
for(int i=chars.length-1;i>=0;i--){
if(chars[i]=='0' && i+consecutiveOnesCount==chars.length-1){
consecutiveOnesCount++;
}else if(chars[i]=='1' && i+consecutiveOnesCount!=chars.length-1){
chars[i]='0';
}else if(chars[i]=='0' && i+consecutiveOnesCount!=chars.length-1){
chars[i]='1';
}
}
String output=new String(chars);
if(consecutiveOnesCount==chars.length){
output="1"+output;
}
System.out.println("2's complement of input is --> "+output);
}
Here the solution in c++:
1-Reverse binary number
2-Add one.
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include<string>
using namespace std;
int main()
{
char bin[]="10011";
int n=(int)strlen(bin);
//1-reverse number
for(int i=0;i<n;i++)
{
if(bin[i]=='1')
bin[i]='0';
else
bin[i]='1';
}
//2-add one to the number
for(int i=n-1;i>=0;i--)
{
if(bin[i]=='0')
{
bin[i]='1';
break;
}
else
bin[i]='0';
}
cout<<"2's complement of is:"<<bin<<endl;
return 0;
}
I don't understand what you mean, can you give an example?
- techinterviewquestion.com February 03, 2016