CODEWITHSUNDEEP
javaalgorithmrecursion
Logan
Logan

Reputation: 1127

Loop through numbers from 0 to 100 and print out every third number without the modulo function using recursion

I had an interview the other day that asked the question, loop through the numbers from 0 to 100 and print out every third number. This is a very easy question if you know what the modulo function is. So I came up with the solution (Note I was using Java): 

for (int i=0; i<100; i++) {
  if (i % 3 == 0) {
    System.out.println(i);
  }
}

He then asked, what if you can't use division or the modulo function. So I had to think about this for about 30 seconds, and came up with a solution, that I knew was very inefficient, and let him know it was very inefficient, but would work. 

int x = 3;
for (int i=0; i<100; i++) {
  for (int j=0; j<33; j++) {
    if (x*j==i) {
      System.out.println(i);
      break;
    } 
  }
}

I'm free writing this without testing, so it might not work 100%, but you get the idea of how I solved the problem. He said he understood what I was trying to do. He then said that there is another way to do it using a recursive function. He tried to briefly explain it to me, but I didn't understand how you could use a recursive function to solve this problem. Can anyone come up with a solution using recursion?

EDIT:

Thanks for all the answers! I didn't think this question would attract as much attention as it did, but I appreciate all the answers. Some of you didn't understand that you can ONLY increment by 1. So you must loop through every natural number from 0 to 100.

Upvotes: 4

Views: 8869

Answers (9)

גלעד ברקן
גלעד ברקן

Reputation: 23955

Another variation on the recursion (JavaScript code):

function f(m,i){
  if (i == 100){
    return;
  } else if (i == 3*m){
    console.log(i);
    f(m + 1,i + 1);
  } else {
    f(m,i + 1);
  }
}

f(0,0);

Upvotes: 1

augray
augray

Reputation: 3161

There is a cool trick to test if a number is divisible by three. If the sum of all its digits is divisible by three, then the original is divisible by three. This can be applied recursively: if I have a number a, I can add all the digits of a together to get b and see if b is divisible by 3. How do I know if b is divisible by three? Add all of its digits together to get c and see if c is divisible by three...

As with all recursion, you have to stop at some point. The base case is when you have a sum which is only one digit long- you can have a list of digits divisible by three and check against these. In code:

public boolean printDivisibleByThrees(){
    for(int i=0; i<100; i++){
        if(isDivisibleByThree(i)){
            System.out.println(i);
        }
    }
}

public boolean isDivisibleByThree(int i){
    if(i<0){
        i = -1*i; //we only care about the absolute value of i
    }
    if(Arrays.asList(0,3,6,9).contains(i)){
        return true;
    } else if(i<10){
        return false; //one digit number not divisible by three
    } else {
        int j = sumDigits(i);
        return isDivisibleByThree(j);
    }
}

public int sumDigits(int i){
    String iString = (new Integer(i)).toString();

    int sum = 0;
    for(char digit : iString.toCharArray()){
        sum += (new Integer(digit+"")).intValue();
    }

    return sum;
}

Upvotes: 4

Daniel Voina
Daniel Voina

Reputation: 3215

Use a second parameter that will keep if the number is or not the third 

public class Rec
{

    public static void rec(int n, int t) {
        if(t==3) {
            System.out.println(n);
            t=0; // reset it
        }
        if(n!=100) {
            rec(++n, ++t);
        }
    }

    public static void main (String[] args)
    {
        rec(0, 3);
    }
}

Upvotes: 2

skypjack
skypjack

Reputation: 50550

I want to add one more answer that is probably unusual, but works fine for each range.
The code is C++ (I'm from mobile and I've only a C++ compiler on it), but it is quite easy to understand and to rewrite in Java.

#include <iostream>

void foo(int c, int n) {
    static int i = 0;

    if(c >= n) return;

    switch(i++) {
    case 1:
    case 2:
        foo(++c, n);
        break;
    case 0:
    case 3:
        std::cout << c << std::endl;
        i = 1;
        foo(++c, n);
    }
}

int main() {
    foo(0, 100);
}

Upvotes: 1

Jorge Campos
Jorge Campos

Reputation: 23371

As no answer has been picked yet I like to add my two cents here. Since the trick is do the modulo function with recursion and without division (as I understood) here is my solution:

public static void main(String[] args) {
    for ( int i = 1; i <=100; i++ ){
        if ( mod(i, 3) ){
            System.out.println(i);
        }
    }
}

public static boolean mod(int a, int b){
    if ( a < 0 ){
        return false;
    }else if (a==b){ 
        return true;
    }else{ 
        return mod( a-b, b );
    }
}

EDIT

This version will handle division by 0 and negative numbers on the modulo function:

public static boolean mod(int a, int b){
    if ( b < 0 ){
        b=b*-1;
    } 
    if ( a < 0 || b == 0){
        return false;
    }else if (a==b){ 
        return true;
    }else{ 
        return mod( a-b, b );
    }
}

Upvotes: 2

brijesh chowdary lavu
brijesh chowdary lavu

Reputation: 129

This would work. !

public class Recursion {

 public static void main(String[] args) {
    myRecursiveMethod(0,1,100,3);
 }

 public static void myRecursiveMethod(int begin,int temp,int end,int n)  
 {  
    if(begin<=end)
    {
        if(temp==n)
        {
            System.out.println(begin);
            temp=0;
        }
        myRecursiveMethod(++begin,++temp,end,n);
    }

 }  

}

Upvotes: -1

Gavriel
Gavriel

Reputation: 19237

void printNth(int max, int n, int i, int sinceLastPrinted) {
    if (i>max) {
        return;
    }
    if (sinceLastPrinted == n-1) {
        System.out.println(i);
        sinceLastPrinted = -1;
    }
    printNth(max, n, i+1, sinceLastPrinted+1);
}

printNth(100, 3, 0, 0);

It's also not 100% clear whether the last number (100 in the example) should be included (if it is "a 3rd number"), depending on that you might need to modify to:

    if (i>=max) {

And also not very clear where to start the "every 3rd"? 0, 3, 6, or 2, 5, 8? The advantage of my function is that this can be easily modified by passing different value for i

Upvotes: 0

asdfasdfadsf
asdfasdfadsf

Reputation: 391

Why not just do:

for (int i = 0; i < 100; i += 3) 
    System.out.println(i);

This way you don't have to check if it is every third number, because it goes up by 3 each time.

Upvotes: 0

torquestomp
torquestomp

Reputation: 3344

One can define the modulus operator using recursion as follows:

// Assume a, b > 0
static int mod(a, b) {
  if (a < b) {
    return a;
  } else {
    return mod(a-b, b);
  }
}

So then you could do:

for (int i=0; i<100; i++) {
  if (mod(i, 3) == 0) {
    System.out.println(i);
  }
}

Upvotes: 1

Related Questions