I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 640 posts at DZone. You can read more from them at their website. View Full User Profile

Thursday Code Puzzler: Harshad Numbers

06.20.2013
| 7179 views |
  • submit to reddit

Thursday - time for another code puzzler. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you find suitable.

Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer.  It's all about the participation!

Harshad Numbers 

Harshad or Niven number is a number that is divisible by the sum of its digits. 201 is a Harshad number because it is divisible by 3 (the sum of its digits.) 

Your challenge is to find all such numbers under 100,000 in the most efficient way possible. Good luck!

Catch up on all our previous puzzlers here




Comments

Igwe Kalu replied on Thu, 2013/06/20 - 2:40am

 Here...

    public static void printHarshadNumbersUnder(int limit) {
        for (int counter = 1; counter < limit; counter++) {
            if (isHarshadNumber(counter)) {
                System.out.println(counter + " is a harshad.\n");
            }
        }
    }

    public static boolean isHarshadNumber(int number) {
        if (number <= 0) {
            throw new IllegalArgumentException("Seriously, you'd do that?");
        }

        if (number <= 9) {
            return true;
        }

        char digits[] = ("" + number).toCharArray();
        int sumOfDigits = 0;

        for (int index = 0; index < digits.length; index++) {
            sumOfDigits += digits[index] - 48;
        }

        return ((number % sumOfDigits) == 0);
    }

Christian Rubiales replied on Thu, 2013/06/20 - 3:33am

public class HarshadNumbers {
	public static void main(String[] args) {
		for (int i = 1; i <= 100000; i++) {
			int sum = 0;
			String s = "" + i;
			for (int j = 0; j < s.length(); j++) {
				sum += Integer.parseInt("" + s.charAt(j));
			}
			if (i % sum == 0) {
				System.out.println(i);
			}
		}
	}
}

Frank Dietrich replied on Thu, 2013/06/20 - 6:17am

a more GC friendly way of @Christians solution

to see the differences run both versions with "-Xloggc:puzzler.log"

public class HarshadNumbers3 {
   public static void main(String[] args) {
      StringBuilder s = new StringBuilder();
      for (int i = 1; i <= 100000; i++) {
         int sum = 0;
         s = s.append(i);
         for (int j = 0; j < s.length(); j++) {
            sum += s.charAt(j) - 48;
         }
         if (i % sum == 0) {
            System.out.println(i);
         }
         s.setLength(0);
      }
   }
}

Rameshkumar Sam... replied on Thu, 2013/06/20 - 6:51am in response to: Frank Dietrich

public class HarshadTest {
       public static void main(String args[]){
               for(int i=11;i<100000;i++){
        boolean isHarshad=isHarshadNumber(i);
        if(isHarshad)
        System.out.println(i);
        }
    }
    private static boolean isHarshadNumber(int number) {
        int sumOfDigits=findSumOfDigits(number);
        if(number%sumOfDigits==0)
        return true;
        return false;
    }
    private static int findSumOfDigits(int number) {
       int sum=0;
       while(number>0){
           sum +=number%10;
           number=number/10;
       }
        return sum;
    }
}

Mark Howard replied on Thu, 2013/06/20 - 7:03am

 In Java, I tried not to use Strings to break up the number:

private static boolean isHarshad(int nNum)
	{
		// Copy the number to check at the end.
		int nOrig = nNum;
		int sum = 0;
		
		LinkedList<Integer> oNumbers = new LinkedList<Integer>();
		
		// Separate each number and add the individual numbers to a list.
		while(nNum > 0)
		{
			oNumbers.add(nNum%10);
			nNum/=10;
		}
		// For each number in the list add it to the sum.
		for(Integer i:oNumbers)
		{
			sum = sum+i;
		}
		// If the original number can be divided by the sum we have a harshad number.
		if(nOrig>0&&nOrig%sum==0)
		{
			return true;
		}
		return false;
	}

Petros Tsialiamanis replied on Thu, 2013/06/20 - 7:34am

import java.util.ArrayList;
import java.util.List;

public class Harshad
{
  private final static int N = 100000;
  public static void main(String[] args)
  {
    long start = System.currentTimeMillis();    
    List<Integer> list = findHarshad(N);
    long end = System.currentTimeMillis();
    System.out.println("Time: " + (end-start) );
//    System.out.println(list);
  }
    
  public static int sumOfDigitsAlt(int n)
  {
    int r = 0;
    while(n!=0)
    {
      r+=n%10;
      n/=10;
    }
    return r;
  }
  
  public static List<Integer> findHarshad(int max)
  {
    List<Integer> list = new ArrayList<Integer>();
    list.add(0);
    for(int i=1; i< max; i++)
    {
        if( isHarshad(i) )
        {
          list.add(i);
        }
    }
    return list;
  }
  
  public static boolean isHarshad(int n)
  {
    return n % sumOfDigitsAlt(n) == 0 ;
  }
}

David Whatever replied on Thu, 2013/06/20 - 10:09am in response to: Petros Tsialiamanis

In Java 8 Streams and Lambdas:

IntStream.range(1,100000)
      .filter(n -> n % 
            Integer.toString(n).chars().map(c -> c - '0').sum() == 0)

Carl Rischar replied on Thu, 2013/06/20 - 2:11pm

A scala attempt

class Harshad( limit:Int ) {	
  val answers = ( for ( i <- 1 to limit ) yield i).filter( arg => isHarshad(arg))
  def isHarshad( n:Int ) : Boolean  = {
    val sumOfDigit = (n.toString()).foldLeft(0)((b,a) => { ( a.toInt - '0'   ) + b } ) 
    if ( (n % sumOfDigit) == 0 ) true else false
  }
}

object Harshad {
  def main( args:Array[String] ) : Unit = {
    val h = new Harshad(100000)
    System.out.println( h.answer )
  }
}

Rafael Naufal replied on Thu, 2013/06/20 - 4:36pm

In Ruby:

(1..99999).select { |n| n % n.to_s.chars.map(&:to_i).reduce(:+) == 0 }

andy darlow replied on Thu, 2013/06/20 - 5:02pm in response to: David Whatever

Its nice to see that java is catching up with the other languages. Can't wait for the official release of Java 8. In the meantime, the scala hack is pretty similar (not the most efficient but simple)...

     (1 to 1000000).filter(x =>  x % (x.toString map(_ asDigit) sum) == 0)

Andy

Kam San replied on Thu, 2013/06/20 - 5:17pm

In Groovy
(1..100000).findAll { it % it.toString()*.toInteger().sum() == 0}

Remigio Di Muzio replied on Fri, 2013/06/21 - 3:25am

I thought this solution which only uses increments to calculate the sum of digits, considering that the sum of digits grows by one at each step from one number to its successor, except that it resets at ten powers.

public class Harshad {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        int num = cycle(5, 0, 0);
    }
    
    private static int cycle(int exp, int num, int s) {
        if (exp == 1) {
            int sum = s;

            for (int i = 0; i < 10; ++i) {
                if (sum != 0 && num % sum == 0) {
                    System.out.println(num + ": " + sum);
                }
                ++sum;
                ++num;
            }
            ++s;
        }
        else {
            for (int i = 0; i < 10; ++i) {
                num = cycle(exp - 1, num, s);
                ++s;
            }
        }
        return num;
    }
}

David Brouse replied on Tue, 2013/06/25 - 9:38am

This example uses recursion in Java to sum the digits:

public class HarshadNumbers {

    public static void main(String[] args) {
        HarshadNumbers harshadNumbers = new HarshadNumbers();
        for (int i = 1; i <= 100000; i++) {
            if (harshadNumbers.isHarshadNumber(i)) {
                System.out.printf("%d\n", i);
            }
        }
    }

    public boolean isHarshadNumber(int i) {
        return (i % sumDigits(i)) == 0;
    }

    private int sumDigits(int i) {
        int sum = i % 10;
        return (i == 0 ? 0 : sum + sumDigits((i - sum) / 10));
    }
}

Rômero De Sousa... replied on Tue, 2013/06/25 - 5:48pm

In Clojure:


(let [char-seq #(str %) int-seq (fn [sq] (map #(- (int %) 48) (char-seq sq)))] (filter #(= 0 (mod (reduce + (int-seq %1)) (count (char-seq %1)))) (range 1 100001)))

Rômero De Sousa... replied on Tue, 2013/06/25 - 5:51pm in response to: Rafael Naufal

It seems that Ruby is slimmer! =)

Fabien Lamarque replied on Thu, 2013/06/27 - 8:32am

 Why do you all go from 1 to 100000? What a waste of time ;)

results: 11781 harshard numbers

Time : 47ms.

the last ones : 89778, 89895, 95979, 96798, 97968, 98787, 99489, 99957, 88998, 99889

view sourceprint?1.private int getSumFigures(int digits){2.    int sum = 0;3.    while ( digits > 0 ){4.        sum += digits % 10;5.        digits /= 10;6.    }7.    return sum;8.}
    @Test
    public void testcount() {
        long time = System.currentTimeMillis();
        List<Integer> harshardList = new ArrayList<Integer>();
        for(int sumOfFigures = 1; sumOfFigures<46 ; sumOfFigures++){
            int figure = sumOfFigures;
            innerloop:
            while(true){
                if(figure>99999){
                    break innerloop;
                }else{
                    if(getSumFigures(figure)==sumOfFigures){
                        harshardList.add(figure);
                    }
                }
                figure +=sumOfFigures;
            }
        }
        long timer = System.currentTimeMillis()-time;
        LOGGER.info(harshardList.toString());      //breakpoint
    }

Steve Shierts replied on Thu, 2013/06/27 - 9:18am

Since no one has bothered trying to use LINQ yet, I threw this together quickly in LinqPad:

Sub Main()

    Dim list = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

    Dim values = (
                    From a In list.where(Function(v) (v <= 1)),
                         b In list.AsParallel(),
                         c In list.AsParallel(),
                         d In list.AsParallel(),
                         e In list.AsParallel(),
                         f In list.AsParallel()
                    Select New With {.number = CLng(String.Format("{0}{1}{2}{3}{4}{5}", a, b, c, d, e, f)),
                                     .total = a + b + c + d + e + f}
                ).skip(1)  '  Skip dividing by 0

    Dim harshadNumbers = (
                            From f In values
                            Where f.number <= 100000 AndAlso f.number Mod f.total = 0
                         )


    harshadNumbers.dump()


End Sub

It is pretty quick less than 35ms on my box.

Benjamin Leroux replied on Thu, 2013/06/27 - 9:43am

In javascript


for (x=0;x<100000;x++){
var t = 0,r=x;
while(r >0){t += r%10;r=Math.floor(r/10);}
if (x % t == 0) console.log(x);
}

Salil Bhole replied on Mon, 2013/07/01 - 3:13pm

My C# Solution:


void Main()
{
	var nums = Enumerable.Range( 1, 100000 )
                .Where( x => x % Convert.ToInt32( x.ToString()
                        .Sum<char>( a => int.Parse( a.ToString() ) ) ) == 0 
                      );
            foreach( var item in nums )
            {
                Console.WriteLine( item );
            }
}

Vivek More replied on Thu, 2013/06/27 - 10:27am

public class HarshadNumber {

    public static void main(final String[] args) {

        final int limit = 10000;

        for (int i = 0; i <= limit; i++) {
            if (isHarshadNumber(i)) {
                System.out.println(i);
            }
        }

    }

    private static boolean isHarshadNumber(final int i) {
        if (i > 0) {
            return i % sumOfDigitsIn(i) == 0;
        }
        return false;
    }

    private static int sumOfDigitsIn(final int i) {
        if (i < 10) {
            return i;
        } else {
            return sumOfDigitsIn(i / 10) + (i % 10);
        }
    }

}

Rimple Shah replied on Thu, 2013/06/27 - 10:31am

 
public class NivenNumber
{
   public static int LIMIT = 100000;

   /**
    *
    *   This program finds all Harshad or Niven number (is a number that is divisible by the sum of its digits ) under 100,000 .
    *
    */
   public static void main(String[] args)
   {
     int sum = 2;
     // first 10 numbres are NivenNo
     for (int i = 1; i <= 10 ; i++)
     {
       System.out.print(i + ", ");
     }
     for(int i = 11; i< LIMIT; i++)
     {
       sum = findSumOfDigits(i);
       
       /*
         increments sum for 9 times, considering that the sum increments one at each step, and resets at ten powers.
        */
       for(int j = 1; j <= 9 ; j++, i++)
       {
         isNivenNumber(i, sum);
         sum++;
       }
         System.out.print(", " + i); // prints power of 10
     }
   }
   
   
    private static void isNivenNumber(int number, int sum)
    {
       //System.out.print(";  number : " + number + " sum : " + sum);
  if(number % sum == 0)
       System.out.print(", " + number);

  }
 
    private static int findSumOfDigits(int number)
    {
    int sum=0;
    while(number>0)
    {
    sum +=number%10;
    number=number/10;
    }
    return sum;
  }

}

Doug Swartz replied on Thu, 2013/06/27 - 5:15pm

In Smalltalk: 

(1 to: 100000) select: 
  [:candidate |
  candidate \\ (candidate asString 
    inject: 0
    into: [:sum :each | sum + each digitValue]) = 0]
In Smalltalk with no String manipulation:
(1 to: 100000) select:
  [ :candidate | |working digitSum|
  digitSum := 0.
  working := candidate.
  [working > 0] whileTrue:
    [digitSum := digitSum + (working \\ 10).
    working := working // 10].
  (candidate \\ digitSum) = 0]

84 ms on my 2 yr old Dell - Windows Experience index processor subscore 7.5

Boris Nebosenko replied on Thu, 2013/06/27 - 12:53pm

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * Created by Boris on 6/27/13.
 */
public class HarshadMain {
    public static void main(String[] args) {
        System.out.print("Enter upper limit for Harshad numbers search: ");
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();

        List<Integer> numbers = getHarshadNumbers(num);

        for (Integer number : numbers) {
            System.out.println(number);
        }

        System.out.println("Total number: " + numbers.size());
    }

    private static List<Integer> getHarshadNumbers(int num) {
        List<Integer> n = new ArrayList<Integer>();

        for (int i = 1; i <= num; ++i) {
            int sum = getDigitsSum(i);

            if ((i % sum) == 0) {
                n.add(i);
            }
        }

        return n;
    }

    private static int getDigitsSum(int number) {
        int sum = 0;
        while (number != 0) {
            sum += number % 10;
            number = number / 10;
        }
        return sum;
    }
}

Enrico Scantamburlo replied on Thu, 2013/06/27 - 1:57pm

 My java version

package harshad;

/**
 *
 * @author Enrico Scantamburlo <scantamburlo at streamsim.com>
 */
public class Harshad {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        long s = System.currentTimeMillis();
        for (int i = 1; i < 10000; i++) {

            if (isHarshad(i)) {
                System.out.println(i);
            }

        }
        long e = System.currentTimeMillis();
        System.out.println("T: " + (e - s));
    }

    protected static boolean isHarshad(int i) {

        int sum = 0;
        int reminder = i;
        while (reminder != 0) {
            int tmp = reminder % 10;
            sum += tmp;
            reminder -= tmp;
            reminder /= 10;
        }

        return i % sum == 0;
    }
}

Attila-mihaly Balazs replied on Thu, 2013/06/27 - 2:29pm

Ugly solution, however it beats other Java code I tried by a factor 6x. Hint: don't use System.out when benchmarking since it will mask all other times (it takes so long you will be essentially measuring System.out).

Tricks:

  • Integer arithmetic
  • Loop unrolling (for 9 consecutive increments we don't need to recalculate the sum, since it will just be incremented by 1)

int counter = 0;
int num = 0, sum = 0;
long time = System.currentTimeMillis();
while (num < 100_000) {
	num += 1;
	sum += 1;
	if ((num % sum) == 0) {
		++counter;
	}

	num += 1;
	sum += 1;
	if ((num % sum) == 0) {
		++counter;
	}

	num += 1;
	sum += 1;
	if ((num % sum) == 0) {
		++counter;
	}

	num += 1;
	sum += 1;
	if ((num % sum) == 0) {
		++counter;
	}

	num += 1;
	sum += 1;
	if ((num % sum) == 0) {
		++counter;
	}

	num += 1;
	sum += 1;
	if ((num % sum) == 0) {
		++counter;
	}

	num += 1;
	sum += 1;
	if ((num % sum) == 0) {
		++counter;
	}

	num += 1;
	sum += 1;
	if ((num % sum) == 0) {
		++counter;
	}

	num += 1;
	sum += 1;
	if ((num % sum) == 0) {
		++counter;
	}

	num += 1;
	sum = 0;
	int val = num;
	while (val != 0) {
		sum += val % 10;
		val = val / 10;
	}
	if ((num % sum) == 0) {
		++counter;
	}
}
System.out.println(System.currentTimeMillis() - time);
System.out.println(counter);

Benjamin Leroux replied on Fri, 2013/06/28 - 3:52am in response to: Attila-mihaly Balazs

30% faster than previous one :

	private static int getNumHarshad() {
		int[] digit = new int[6];
		int counter = 0;
		for (int i = 1; i < 100000; i++) {
			inc(digit, 0);
			if (i % (digit[0] + digit[1] + digit[2] + digit[3] + digit[4] + digit[5]) == 0) {
				counter++;
			}

		}
		return counter;
	}

	private static void inc(int[] digit, int index) {
		digit[index]++;
		if (digit[index] == 10) {
			digit[index] = 0;
			inc(digit, index + 1);
		}
	}

Lars Bendixen replied on Sat, 2013/06/29 - 5:15pm

...

Remigio Di Muzio replied on Sun, 2013/06/30 - 1:53am in response to: Benjamin Leroux

I've revised my algorithm in order to check execution time and comparing it with others, upon modifying them to use the same method of inserting Harshad numbers in a list.

My one is slightly faster by 1~2 ms, having almost everytime an 11 ms execution time, while others make no better than 12~13. Can anyone make the same test?

public class HarshadTest {
    private static List<Integer> list = new LinkedList<>();
    
    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        findHarshad(5, 0, 0);
        long end = System.currentTimeMillis();
        System.out.println("Time: " + (end-start) );
        System.out.println(list);
    }
    
    private static int findHarshad(int exp, int num, int s) {
        if (exp == 1) {
            int sum = s;

            for (int i = 0; i < 10; ++i) {
                if (sum != 0 && num % sum == 0) {
                    list.add(num);
                }
                ++sum;
                ++num;
            }
            ++s;
        }
        else {
            for (int i = 0; i < 10; ++i) {
                num = findHarshad(exp - 1, num, s);
                ++s;
            }
        }
        return num;
    }
}

Bob Beechey replied on Mon, 2013/07/01 - 10:37pm

As always a "quick and dirty" Python coding is very easy to read and understand.

 

def sumofdigits(num):
    s=str(num)
    result=0
    for ss in s:
        result+=int(ss)
    return result

def isharshad(num):
    return num%sumofdigits(num)==0

for number in range(1,10001):
    if isharshad(number):
        print(number)


 

Paul Murray replied on Sun, 2014/01/26 - 7:42am

 The largest number is 999,999, so the largest possible digit sum is 54. So you could prepare a boolean  array 54 by LCM(1-54) which is … ok, just a shade too big. Scotch that idea. Make it instead a manageable composite number - 2*2*2*3*3*5 is 360.

So we make an array 54 by 360. Each cell, we mark it true if the digit sum (1-54) is definitely a factor of any number for which mod360 is equal to the column. For instance, for any number x where x%360==5, if the digit sum is 5 then  it will definitely divide. (I thik we are gong to have to go bigger than 360, just sayin').

Step through the numbers. Each time we do, the number mod360 increments. The digit sum increments except for every 10th step, where it decrements by 8, unless its a 100th step in which case it decrements by 17 - etc. we use this to look up the array. If it's true, then we need to look no further. Otherwise, we are going to have to do it the hard way with a modulus operation. Happily, we are keeping track of the digit sum as we go, so the hardest bit is already done.

Anyway. Here's the fun bit - computation of the digit sum. We avoid taking moduluses

  public static void main(String[] args) {

  int mod10 = 10;
  int mod100 = 100;
  int mod1000 = 1000;
  int mod10000 = 10000;
  int mod100000 = 100000;

  int digitsum = 0;
  int x = 0;

  while (x < 1020) {
  System.out.println("Digit sum of " + x + " is " + digitsum);
   
  // System.out.println(mod100000 + ", " + mod10000 + ", " + mod1000 + ", " + mod100 + ", " + mod10);
   

  x++;

  if (--mod10 != 0) {
  mod100--;
  mod1000--;
  mod10000--;
  mod100000--;
  digitsum++;
  continue;
  }

  mod10 = 10;

  if (--mod100 != 0) {
  mod1000--;
  mod10000--;
  mod100000--;
  digitsum += 1 - 9;
  continue;
  }

  mod100 = 100;

  if (--mod1000 != 0) {
  mod10000--;
  mod100000--;
  digitsum += 1 - 9 * 2;
  continue;
  }

  mod1000 = 1000;

  if (--mod10000 != 0) {
  mod100000--;
  digitsum += 1 - 9 * 3;
  continue;
  }

  mod10000 = 10000;

  if (--mod100000 != 0) {
  digitsum += 1 - 9 * 4;
  continue;
  }

  // mod 1000000 is always nonzero because we stop before there

  mod100000 = 100000;
  digitsum += 1 - 9 * 5;
  continue;
  }
  }

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.