Country: India

Comment hidden because of low score. Click to expand.
4
of 4 vote

Ok, no use of the - operator either. Here we go:

``````//current value is the result so far mod 3
currentValue = 0;

//if number is negative, flip the bits and add 1
if (input < 0)
{
input = ~input;
currentValue = 1;
}

//current multiplier is 2^n mod 3, if I'm currently processing the n-th least significant
//bit counting from 0. This quantity doubles every time I move 1 bit to the left, so mod 3
//it will alternate between 1 and 2.  2^0 mod 3 = 1, 2^1 mod 3 = 2, 2^2 mod 3 = 1, ...
currentMultiplier = 1;

//while the input still has unprocessed bits
while (input != 0)
{
//input & 1 gets the value of the least significant bit
//if bit is 0, we add nothing to the current value;
//otherwise we do this...
if (input & 1 == 1)
{
// we want to achieve currentValue
// = (currentValue+ currentMultiplier) % 3,
// but we'll have to do it finite state machine-style
if (currentValue == 0)  { currentValue = currentMultiplier; }
if (currentValue == 1) { currentValue = (currentMultiplier == 1) ? 2: 0; }
if (currentValue == 2) { currentValue = (currentMultiplier == 1) ? 0: 1; }
}

//multiply current multiplier by 2 mod 3
currentMultiplier = (currentMultiplier == 1) ? 2: 1;

//logical shift to remove the bit just processed
input = input >>> 1;
}``````

Comment hidden because of low score. Click to expand.
0

And then you want to

return (currentValue == 0);

Comment hidden because of low score. Click to expand.
0

bingo....awesome solution

Comment hidden because of low score. Click to expand.
0

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");

}

Comment hidden because of low score. Click to expand.
0

I guess using % is not allowed..wrong solution.

Comment hidden because of low score. Click to expand.
0

% is not used anywhere in the code!!

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}``````

Comment hidden because of low score. Click to expand.
0

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)

Comment hidden because of low score. Click to expand.
0

I take it that it's not OK to use the - operator. I think the intent is to use bit operators.

Comment hidden because of low score. Click to expand.
0
of 2 vote

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

Comment hidden because of low score. Click to expand.
0

Condition is to NOT use any of the +,-,/,* operations

Comment hidden because of low score. Click to expand.
0

Condition is to NOT use any of the +,/,* operations, so using substraction seems to be the solution

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

Can we substititue + with --? Two minus = one plus.

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

If '+' is also not allowed, you can use '|' operator.e.g. if number is 123, res=1|2|3;
res will be equal to 3,6 or 9 if number is divisible by 3

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def divisible_by_3(n):
m = -n

while m < -9:
s_m = str(m)
m = 0
for c in s_m[1:]:
m -= int(c)

if m == -3 or m == -6 or m == -9:
return True
return False``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

It can be done by counting the odd and even set bits in the number.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int co(int n) // return 1 if true
{
int c=1;
while(n!=0)
{
n&=(n-1);
c=c^1;
}

return c;
}``````

Comment hidden because of low score. Click to expand.
0

BRILLIANT

Comment hidden because of low score. Click to expand.
0

brilliant solution

but could you please explain the logic behind this.

Comment hidden because of low score. Click to expand.
0

@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

Comment hidden because of low score. Click to expand.
0

It doesn't work for values like 40, 80, 160, 320 etc.

Comment hidden because of low score. Click to expand.
0

``It doesn't work for 40, 80, 160, 320 etc``

Comment hidden because of low score. Click to expand.
0
of 0 vote

bool divby3(unsigned int x)
{
int n = x>>1, m;
while(1)
{
m = x - n << 1;

if(m == n)
return false
else if(m > n)
return true;
else
n--;
}

// should never be here
}

// can we use "-"?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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")

Comment hidden because of low score. Click to expand.
0
of 0 vote

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")

Comment hidden because of low score. Click to expand.
0
of 0 vote

======================================
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);
}

}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple code is here

public class EvenandOddNumber {
public static void main(String[] args) {
int i=5;
int j=i&1;
if(j>0){
System.out.println("odd");
}
else {
System.out.println("even");
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<conio.h>
int main()
{
int n,i,f=0;
printf("enter the number:\n");
scanf("%d",&n);
for(i=0;i<n;i=i-3)
{
if(i==0)
{
f=1;
break;
}
}

if(f==1)
{
printf("%d is divisible by 3",n);

}
else
{
printf("%d is not divisible by 3",n);
}
return 0;
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

i did not see "-" operator in the question, can we use it?
in that case :
(number << 2 )- number)

Comment hidden because of low score. Click to expand.
0

ignore this comment, it is actually multiplying the number by 3

Comment hidden because of low score. Click to expand.
0

Yep, this one's completely wrong.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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".

Comment hidden because of low score. Click to expand.
0

We aren't allowed to use the % operator.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.