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 639 posts at DZone. You can read more from them at their website. View Full User Profile

Thursday Code Puzzler: Playing With Numbers

06.14.2012
| 4341 views |
  • submit to reddit

By now you should be familiar with our Thursday Code Puzzler slot. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you think is 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!

This weeks question is about deconstructing numbers to find digits that match a certain pattern.

Write a method that would find all positive integers that do not have 0 in their digits, and have a digital sum equal to 5. An example of this would be 14  (1+4 =5). 

Output what each of the numbers are and, as usual, aim for efficiency in your answer

Thanks to everyone who participated in last weeks question, providing some great solutions. 

Comments

Jarek Acyrf replied on Thu, 2012/06/14 - 2:54am

Java solution for a good start:

 
public class Digitizer {
    static final int SUM_MAX=5;
    static int[] digits=new int[SUM_MAX];
   
    static void addDigit(int digitNum, int digitSum){
        int digit=1;
        for (;digit<SUM_MAX-digitSum;digit++){
            digits[digitNum]=digit;
            addDigit(digitNum+1,digitSum+digit);
        }
        printDigit(digitNum,digit);
    }
   
    static private void printDigit(int digitNum,int lastDigit) {
        for (int i=0;i<digitNum;i++)
            System.out.print(digits[i]);
        System.out.println(lastDigit+"\n");
    }

    static public void main(String[] params){
        addDigit(0,0);
    }
}

Mrd Mind Your B... replied on Thu, 2012/06/14 - 4:00am

// under 30milli

public class TestSumOfFive extends TestCase {

	public void testSumOfFive() {

		long start = System.currentTimeMillis();
		StringBuffer bf = new StringBuffer();
		for (int i = 14; i <= 11111; i++) {
			String numberString = Integer.toString(i);
			if (numberString.contains("0") || numberString.contains("5")
					|| numberString.contains("6") || numberString.contains("7")
					|| numberString.contains("8") || numberString.contains("9")) {
				continue;
			} else {
				int count = 0;
				for (int j = 0; j < numberString.length(); j++) {
					count += Integer.parseInt(Character.toString(numberString
							.charAt(j)));
					if (count > 5) {
						break;
					}
				}
				if (count == 5) {
					bf.append(i);
					bf.append("\n");
				}
			}
		}
		System.out.println(System.currentTimeMillis() - start
				+ " millisenconds");
		System.out.println(bf);
	}

}

Jarek Acyrf replied on Thu, 2012/06/14 - 4:20am in response to: Mrd Mind Your Business

Jeez... My solution even without buffering the output printing gives me always 0ms...

Probably faster PC...

;)

Mrd Mind Your B... replied on Thu, 2012/06/14 - 4:21am in response to: Jarek Acyrf

yeap ... mine was a terrible solution. 

Jason Shin replied on Thu, 2012/06/14 - 5:09am

import java.util.*;

public class Honesty {

	public static void main(String[] args) {
		int MAX_DIGIT = 5;
		int START_DIGIT = 1;
		ArrayList<Integer> al = new ArrayList<Integer>();

		for(int i = 0; i < MAX_DIGIT; i++){
			for (int j = 0; j < MAX_DIGIT; j++) {
				if ( ( (MAX_DIGIT - j) + (START_DIGIT + i) ) == 5 ) {
					al.add( (START_DIGIT + i) * 10 + MAX_DIGIT - j);
				}
				if ( ( (MAX_DIGIT - i) + (START_DIGIT + j) ) == 5 ){
					al.add( (MAX_DIGIT - i) * 10 + START_DIGIT + j);
				}
			}
		}
		System.out.println("There are " + al.size() + " numbers that are added to become 5 \nAnd list is: " + al);
	}

}

Jason Shin replied on Thu, 2012/06/14 - 5:10am

is this how you do it? lol

i hope it's correct

Jason Shin replied on Thu, 2012/06/14 - 5:28am

Mine took 2 or 1 milli sec

Jason Shin replied on Thu, 2012/06/14 - 5:35am in response to: Jason Shin

wait, i didn't consider 1+1+1+1+1 lol and all the others

Mrd Mind Your B... replied on Thu, 2012/06/14 - 6:00am

Jarek Acyrf was the best although it prints number 5 .
I didn't think about using recursivity and avoiding buffering the output... I will get it next time

Jarek Acyrf replied on Thu, 2012/06/14 - 6:46am in response to: Mrd Mind Your Business

Hey, What's wrong with 5? Sum of its digits give 5. In my opinion not writing 5 is an error!

Robert Stern replied on Thu, 2012/06/14 - 6:59am

Considering 5 as acceptable value: (otherwise change count start from 14 and 53 to 52)

 StringBuffer buffer = new StringBuffer();
        start = System.currentTimeMillis();
        for (int count = 5; count <= 11111; count++) {
            String daNumber = String.valueOf(count);
            int sum = 0;
            for (int i = 0; i < daNumber.length() && sum < 6; i++) {
                if (daNumber.charAt(i) == 48 || daNumber.charAt(i) > 53) {
                    sum = 6;
                    break;
                }
                sum += daNumber.charAt(i) - 48;
            }
            if (sum == 5) {
                buffer.append(daNumber);
                buffer.append("\n");
            }

        }
        System.out.println(System.currentTimeMillis() - start + " millisenconds");

System.out.println(buffer); 

Jarek Acyrf replied on Thu, 2012/06/14 - 8:16am

Version a bit modified and optimized for displaying the result.

For 1 000 000 repetitions on my PC it is still below 3 seconds!

public class Digitizer {
static final int SUM_MAX=5;//WORKS only for 1-9
static int[] digits=new int[SUM_MAX];
static StringBuilder buffer = new StringBuilder();

static void addDigit(int digitNum, int digitSum){
int digit=1;
for (;digit<digitSum;digit++){
digits[digitNum]=digit;
addDigit(digitNum+1,digitSum-digit);
}
digits[digitNum]=digit;
printDigit(digitNum);
}

static private void printDigit(int digitNum) {
for (int i=0;i<=digitNum;i++)
buffer.append((char)('0'+digits[i]));
buffer.append("\n");
}

static public void main(String[] params){
long start = System.currentTimeMillis();
for (int i=0;i<1000000;i++){
buffer.setLength(0);
addDigit(0,SUM_MAX);
}
System.out.println(System.currentTimeMillis() - start + " millisenconds");
System.out.println(buffer);
}
}

Octavian Ciubotaru replied on Thu, 2012/06/14 - 8:40am

public class Print5 {
    
    int t[] = new int[5];
    
    void find(int size, int sum) {
        if (sum==5) print(size);
        for (int d=1;d<=5-sum;d++) { t[size]=d; find(size+1, sum+d); }
    }
    
    void print(int size) {
        for (int i=0;i<size;i++) System.out.print(t[i]);
        System.out.println();
    }
    
    public static void main(String[] args) {
        new Print5().find(0,0);
    }
}

Greg Allen replied on Thu, 2012/06/14 - 9:24am

print [x for x in range(11112) if '0' not in str(x) and sum(int(i) for i in str(x))==5]

 >>> timeit.timeit("[x for x in range(11112) if '0' not in str(x) and sum(int(i) for i in str(x))==5]", number=1000)
37.977932988308396

 i.e. 38ms

Erin Garlock replied on Thu, 2012/06/14 - 10:36am

Why is everyone stopping at 11111?  20000 (5 digits) & 200000000000 (12 digits) still only sum their digits to 1.

To brute force it you have to go 0 -> Integer.MAX_VALUE.  This is in the same vein as the Tower of Hanoi problem.  If nobody posts an answer sooner I'll do so this weekend.

Greg Allen replied on Thu, 2012/06/14 - 10:45am in response to: Erin Garlock

that do not have 0 in their digits

Erin Garlock replied on Thu, 2012/06/14 - 11:02am

As per the requirements, find ALL Integers - Assuming java, Integer.MAX_Value = 2^31-1 = 2,147,483,647 (10 digits)

Erin Garlock replied on Thu, 2012/06/14 - 11:04am

doh - I missed the "does not have zeros"

Rajeesh Tripathi replied on Thu, 2012/06/14 - 11:44am

#include <iostream>
using namespace std;

int main() {

	int minVal = 1;
	int maxVal = 4;
		
	for (int i = minVal; i <= maxVal; i++) {
		for (int j = maxVal; j >= minVal; j--) {
			int val = i + j;
			if (val == 5)
				cout << i << j << endl;
			}
		}
	return 0;
}

time ./SolvePuzzle
14
23
32
41

real 0m0.002s
user 0m0.000s
sys 0m0.001s

Vijay Nathani replied on Fri, 2012/06/15 - 12:04pm

Groovy solution that prints: 11111, 1112, 1121, 113, 1211, 122, 131, 14, 2111, 212, 221, 23, 311, 32, 41, 5

void giveNumbers(expectedTotal, previousNumbers=[]) {
	if (previousNumbers.sum() == expectedTotal) println previousNumbers.join("")
	(expectedTotal - previousNumbers.sum(0)).times { giveNumbers(expectedTotal, previousNumbers + ++it) }
}
giveNumbers(5)

 

 

Rajeesh Tripathi replied on Thu, 2012/06/14 - 11:50am in response to: Rajeesh Tripathi

hmm.. it does not work for 221 or 122 and many other combos...

Der Meister replied on Thu, 2012/06/14 - 11:50am

Here's the generalized non-recursive optimized version for any sum of digits.

It's limited by the amount of memory needed to store the 2^(sum-1) calculated numbers (for sums up to 9, fewer numbers for sums > 9).

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

public class DigitSum {

    private int sum;
    
    public DigitSum(int sum) {
        this.sum = sum;
    }

    public List<String> calculate() {
        List<String> nums = new ArrayList<String>(1 << (sum-1));
        char d[] = new char[sum];
        int sumd = 0;
        int i = 0;
        d[i] = '0';
        while (i >= 0) {
            sumd++;
            d[i]++; 
            if (sumd == sum && d[i] <= '9') nums.add(new String(d,0,i+1));
            if (sumd >= sum || d[i] > '9') {
                sumd -= d[i--] - '0';
            } else {
                d[++i] = '0';
            }
        }
        return nums;
    }
    
    public static void main(String[] args) {
        int sum = args.length > 0 ? Integer.parseInt(args[0]) : 5;
        List<String> nums = new DigitSum(sum).calculate();
        for (int i=0; i<nums.size(); i++) System.out.println(nums.get(i));
        System.out.println("=== "+nums.size()+" Numbers ===");
    }
}

 

Mitch Mccuiston replied on Thu, 2012/06/14 - 12:34pm

Solution in Scala
(5 to 11111).
map(_.toString()).
filter(str => !str.contains("0") && str.foldLeft(0)((sum,digit)=>sum+digit-'0')==5).
foreach(println)

Earnest Dyke replied on Fri, 2012/06/15 - 6:32am

Code:

package com.ferguson.codepuzzler;

import org.junit.Test;

public class DigitsEqual5 {

	@Test
	public void digitsEqual5() {
		int sum = 0, j = 0;
		loop1: for (int i = 5; i <= 11111; i++) {
			String num = Integer.toString(i);
			if (num.matches(".*0+.*")) {
				continue;
			}
			sum = 0;
			for (j = 0; j < num.length(); j++) {
				sum += Integer.parseInt(num.substring(j, j + 1));
				if (sum > 5) {
					continue loop1;
				}
			}
			if (sum == 5) {
				System.out.println(num);
			}
		}
	}
}

Results:

 5
14
23
32
41
113
122
131
212
221
311
1112
1121
1211
2111
11111
Earnie!

 

Neeraj Khapre replied on Fri, 2012/06/15 - 7:53am

public class PlayingWithNubers {
    public static void main(String[] args) {        
        int size = 100000000;        
        long startTime = System.currentTimeMillis();        
        for (int i = 0; i < size; i++) {
            char[] arrNum = String.valueOf(i).toCharArray();
            int sum = 0;
            int count = 0;

            for (int j = 0; j < arrNum.length; j++) {
                if (Integer.parseInt(String.valueOf(arrNum[j])) == 0) {
                    count++;
                    break;
                } else {
                    if (count < 1)
                        sum = sum + Integer.parseInt(String.valueOf(arrNum[j]));
                }
            }
            if (count < 1 && sum == 5)
                System.out.println(">>> Number is : " +i + "   and sum is " + sum);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("Total time taken for size = 100000000 is "+(endTime-startTime)/1000 +" seconds.");

    }
}

 

Result: For size = 100000000

 >>> Number is : 5   and sum is 5
>>> Number is : 14   and sum is 5
>>> Number is : 23   and sum is 5
>>> Number is : 32   and sum is 5
>>> Number is : 41   and sum is 5
>>> Number is : 113   and sum is 5
>>> Number is : 122   and sum is 5
>>> Number is : 131   and sum is 5
>>> Number is : 212   and sum is 5
>>> Number is : 221   and sum is 5
>>> Number is : 311   and sum is 5
>>> Number is : 1112   and sum is 5
>>> Number is : 1121   and sum is 5
>>> Number is : 1211   and sum is 5
>>> Number is : 2111   and sum is 5
>>> Number is : 11111   and sum is 5


Total time taken for size = 100000000 is 47 seconds.

 

Heidi Elliott replied on Fri, 2012/06/15 - 10:25am

Another groovy version:

def list = []

0.upto(Integer.MAX_VALUE) { number ->
  def string = number.toString()
  if ( !string.contains('0') && (string.inject(0) { sum, value -> sum += value.toInteger(); return sum } == 5) ) { list << number }
}

list.join(", ") 

Output: 5, 14, 23, 32, 41, 113, 122, 131, 212, 221, 311

 

 

 

 

 

 

 

Amir Pashazadeh replied on Fri, 2012/06/15 - 6:29pm

My solution:

 

public class Main {
    private static final int TARGET_NUMBER = 5;
    private static Collection<Integer> result = new HashSet<Integer>();

    public static void findSolution(int currentDigitCount, int previousSum, int currentValue) {
        if (currentDigitCount <= TARGET_NUMBER) {
            for (int i = (currentValue > 0 ? 1 : 0); i <= TARGET_NUMBER - previousSum; i++) {
                if (previousSum + i == TARGET_NUMBER) {
                    result.add(currentValue * 10 + i);
                } else if (currentDigitCount < TARGET_NUMBER) {
                    findSolution(currentDigitCount + 1, previousSum + i, currentValue * 10 + i);
                }
            }
        }
    }

    public static void main(String[] args) {
        long start = System.nanoTime();
        findSolution(0, 0, 0);
        long end = System.nanoTime();

        for (Integer integer : result) {
            System.out.println(integer);
        }

        System.out.println("Time: " + (end - start));

    }
}

 

It takes about 150000 nano seconds on my PC.

Valery Silaev replied on Fri, 2012/06/15 - 6:40pm

package main;

public class Digi {
	public static void main(final String argv[]) {
		final long startTime = System.currentTimeMillis();
		for (int i = 11111; i >= 5; i--) {
			//final Collection<Integer> digets = new ArrayList<Integer>(5);
			int sum = 0;
			int v = i;
			for (; v > 0 && sum < 5; v /= 10) {
				final int diget = v % 10;
				if (diget == 0) {
					sum = 6; // exit early
				} else {
					//digets.add(diget);
					sum += diget;
				}
			}
			if (sum == 5 && v == 0)
				System.out.println(i /*+ " = " + digets*/);
		}
		System.out.println("Time: " + (System.currentTimeMillis() - startTime));
	}

Output:
11111
2111
1211
1121
1112
311
221
212
131
122
113
41
32
23
14
5
Time: 1

i.e. 1ms
 

Mo Gaembo replied on Mon, 2012/06/18 - 4:39pm

for(Integer i=0;i<106000;i++)               

{                                 

            int k = i;                                   

            int temp = 0;                            

            while(k > 9)                              

            {                                             

                        if((k%10 == 0)||(k/10 > 4 && k/10 < 10)) {k=0;temp=0; break;}                                    

                        temp = temp + (k%10);                                    

                        k = k/10;                                             

                        if (k < 5) {                                                       

                                    temp = temp + k;                                             

                        }                                 

            }                                 

            if(i == 5 || temp == 5)                          

            {                                             

                        System.err.println("........."+i+".........");                         

            }

}


Mo Gaembo replied on Mon, 2012/06/18 - 4:44pm

public class MyPuzzle1 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		new MyPuzzle1().doSomething();

	}

	private  void doSomething() {
		for(int i=0;i<Integer.MAX_VALUE;i++)
		{
			int k = i;
			int temp = 0;
			while(k > 9)
			{
				if((k%10 == 0)||(k/10 > 4 && k/10 < 10)) {k=0;temp=0; break;}
				temp = temp + (k%10);
				k = k/10;
				if (k < 5) {
					temp = temp + k;
				}
			}
			if(i == 5 || temp == 5)
			{
				System.err.println("........."+i+".........");
			}
		}
	}

}

Comment viewing options

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