## rai.kaushal

BAN USERThis is a question related to DFA - Automata for a numberdivisible by 3.

:). You don't really need those standard mathematical operators. Bit shift & XOR operators would be at your help.

1) First if the number is negative, remove the negative sign by either string manipulation or any other way you like and get each digit in array/list using the XOR operator. Eg

num = 5 (101)

d1 = 5 ^ 1 = 1, num=num >> 1

d2 = 2 ^ 1 = 0 , num = num >> 1

d3 = 1 ^ 1 = 1

Now access the binary representation in reverse order - d3, d2, d1 in the loop

Say the number is in list digitList.

int initialState = 0

for(i=digitList.size(); i >=0; i--){

if(digitList.get(i)==0){

if(initialState==0)

// initialState = 0 :: No change in state in this case.

else if(initialState == 1)

// Change the state to next value 2

initialState = 2

else

// Change the state to next value 1

initialState = 1

}else if(digitList.get(i)==1){

if(initialState==0)

initialState = 1

else if(initialState == 1)

// Change the state to next value

initialState = 0

else

// initialState = 2 :: In this case, as per automata, we do not change the state

}

}

if(initialState == 0)

// Number is divisible by 3

Sysout("Number is divisible by 3")

else

Sysout("Number is NOT divisible by 3")

This is a question related to DFA - Automata for a numberdivisible by 3.

:). You don't really need those standard mathematical operators. Bit shift & XOR operators would be at your help.

1) First if the number is negative, remove the negative sign by either string manipulation or any other way you like and get each digit in array/list using the XOR operator. Eg

num = 5 (101)

d1 = 5 ^ 1 = 1, num=num >> 1

d2 = 2 ^ 1 = 0 , num = num >> 1

d3 = 1 ^ 1 = 1

Now access the binary representation in reverse order - d3, d2, d1 in the loop

Say the number is in list digitList.

int initialState = 0

for(i=digitList.size(); i >=0; i--){

if(digitList.get(i)==0){

if(initialState==0)

// initialState = 0 :: No change in state in this case.

else if(initialState == 1)

// Change the state to next value 2

initialState = 2

else

// Change the state to next value 1

initialState = 1

}else if(digitList.get(i)==1){

if(initialState==0)

initialState = 1

else if(initialState == 1)

// Change the state to next value

initialState = 0

else

// initialState = 2 :: In this case, as per automata, we do not change the state

}

}

if(initialState == 0)

// Number is divisible by 3

Sysout("Number is divisible by 3")

else

Sysout("Number is NOT divisible by 3")

Take 3 pointers to the starting point of the list - P1, P2 & P3.

Start moving P1 & P3 till you have moved 'K' nodes. If the list ends before P1 reaches the End, give the error message "LIST IS OF LESSER SIZE".

Once you have reached the Kth node, move P1 and P2 pointers to the next node one by one till P1 reaches the end.

At this point P2 points to the Kth element from the last.

Now simply swap the values of P2 & P3.

Job done.

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

In these types of questions you are explicitly asked not to use any complex inbuilt data structure. Hence do not use HashSet/HashMap.

- rai.kaushal May 15, 2012Also, these questions require some limited amount of extra memory usage.

The best answer i thought has already been given by 'to google' as first reply.