Adobe Interview Question
Country: India
code would be something like
main()
{
int a,i=2,b=0,j=0,k=0;
scanf("%d",&a);
while(a)
{
b= a&1;
if(i == 2)
i=1;
else
i=2;
if(b)
{
if(j==0)
j=j+i;
else if (j== 1)
{
if(i==2)
j=0;
else
j=2;
}
else if (j==2)
{
if(i==2)
j=1;
else
j=0;
}
}
a=a>>1;
}
if(j == 0)
printf("number is divisible by 3");
else
printf("number is not divisible by 3");
}
int dividebyzero(int n)
{
while(n>0)
n=n-3;
// if n = 0 then number is divisible by 3 and return 1 (true)
// if n = -1 or -2 then number is not divisible by 2 and return 0 (false)
return (n)?0:1;
}
2 questions:-
1. What if the input is too large??(10000 digits, suppose)
2. What if the input is in another base?(u assumed decimal, i perceived)
Convert number to string and add each digit.
Do this until the sum is less than 10
if the number is 3, 6,9 it is divisible by 3
Condition is to NOT use any of the +,/,* operations, so using substraction seems to be the solution
I'm pretty sure the poster just forgot to mention that it's also not OK to use the - operator. Otherwise, you could emulate the + operator all too easily, and with a + operator you can make a * operator easily, and with a * operator you can make a % operator easily.
That's precisely why I think the use of - wouldn't have been allowed for this question either. It is in fact possible to solve this question with only bitwise operations.
This is on the principle if total of all the digits of number is divisible by 3 then number itself is divisible by 3.
Check java implementation here, at least all my tests are positive.
Assumption... did for the positive numbers.
public class DivByThree {
/**
* @param args
*/
public static void main(String[] args) {
System.out.println(divByThree(102) + " Now recheck div calc:-" + (102%3));
System.out.println(divByThree(101) + " Now recheck div calc:-" + (101%3));
System.out.println(divByThree(111111111) + " Now recheck div calc:-" + (111111111%3));
System.out.println(divByThree(11111111) + " Now recheck calc:-" + (11111111%3));
System.out.println(divByThree(12992111) + " Now recheck calc:-" + (12992111%3));
System.out.println(divByThree(129921117) + " Now recheck calc:-" + (129921117%3));
}
private static boolean divByThree(int intVal) {
String strVal = "" + intVal;
int total = 0;
for (char c : strVal.toCharArray()) {
total = total + (int) c;
}
while (total > 0)
total = total - 3;
return (total == 0) ? true : false;
}
}
int co(int n) // return 1 if true
{
int c=1;
while(n!=0)
{
n&=(n-1);
c=c^1;
}
return c;
}
@feiskyer
u r counting number of set bits in n
and flipping c every time
hence if number of 1's are even answer is true
else false
but it's not the condition for divisibility by 3
e.g. n=5 or 101 in binary
number of set bits = 2
and your solution will give true but it's wrong
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")
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")
======================================
DOUBT: Please confirm, can we use increment operator (++) in this problem or not. B'coz increment operator is not am arithmetic operator thats why I used it.
If we can't do it with help of increment operator we should use bitwise oprator. Please suggest with clear explanation.
======================================================
public class CodeTestingPurpose {
public static void main(String args[]){
CodeTestingPurpose c = new CodeTestingPurpose();
c.funct(33);
}
void funct(int num){
int count = 0;
if(num == 3){
System.out.println("number is divisible by 3");
}
else if(num < 3){
System.out.println("number is not divisible");
}
else{
for(int j = 3; j < num; j++){
count++;
}
num = count;
funct(num);
}
}
}
fun_div_3(int testNum)
{
for (i = 1;i<= testNum/2;i++)
{
//if x is divisible by 3 then we have x/3 = y where y belongs to Intezer
// => x = 3*y
//=> x = (2^2 - 1) *y
//=> x = (2^2)*y - y;
//=> x = y>>2 - y
if(testNum == (i>>2 - i))
{
printf(" %d is divisible by 3",testNum);//Without using /,% ,+and * operators.Mind ittttaaaa :)
break;
}
}
}
i did not see "-" operator in the question, can we use it?
in that case :
(number << 2 )- number)
The question said "and" not "or"; thus, my answer is very simply:
boolean divisibleBy3(int n) {
return (n%3)==0;
}
I did not use all of the operators stated, only one of them; thus I did not use the union of them. If they want a better answer, they can learn to write a better question. Btw, question says "nor" instead of "not".
Ok, no use of the - operator either. Here we go:
- eugene.yarovoi April 12, 2012