How Many Distinct Products In A Times Table?

July 15, 2014

We all learned our times tables in elementary school. For instance, here is the standard 9 by 9 times table:

1  2  3  4  5  6  7  8  9
2  4  6  8 10 12 14 16 18
3  6  9 12 15 18 21 24 27
4  8 12 16 20 24 28 32 36
5 10 15 20 25 30 35 40 45
6 12 18 24 30 36 42 48 54
7 14 21 28 35 42 49 56 63
8 16 24 32 40 48 56 64 72
9 18 27 36 45 54 63 72 81

That table has 36 distinct products: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, 28, 30, 32, 35, 36, 40, 42, 45, 48, 49, 54, 56, 63, 64, 72 and 81.

Your task is to write a program that computes the number of distinct products in an n by n times table. There is an obvious O(n2) algorithm; can you do better? When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

5 Responses to “How Many Distinct Products In A Times Table?”

  1. Graham said

    Trying to jump back on the Lisp/Scheme train. Here’s a Common Lisp version:

    (defun m (n)
      "ProgPraxis's sieve solution to
      'How Many Distinct Products in a Time Table?'"
      (let ((bits (make-array (1+ (* n n))
                              :element-type 'bit
                              :adjustable nil)))
        (loop for i from 1 to n do
              (loop for j from (* i i) to (* i n) by i
                    do (setf (elt bits j) 1)))
        (loop for b across bits summing b)))
    
  2. Nick said

    How can I improve this?

    import java.util.*;
    
    
    public class ft {
    
    	/**
    	 * @param args
    	 */
    	public static void main(String[] args) {
    		int a=0,e=0; //e by a times table
    		Scanner input = new Scanner(System.in);
    		
    		while(true) {
    			try {
    			System.out.print("Enter # of columns: ");
    			String consoleInput = input.nextLine();
    			e = Integer.parseInt(consoleInput);
    			break;
    			}
    			catch (Exception ex) {
    				System.out.println("#s Only!");
    				
    			}
    			}
    		while(true) {
    				try {
    			System.out.print("Enter # of rows: ");
    			String consoleInput = input.nextLine();
    			a =Integer.parseInt(consoleInput);
    			break;
    				}
    				catch (Exception ex) {
    					System.out.println("#s Only!");
    					
    				}
    			}
    		
    		
    		
    		ArrayList<ArrayList<Integer>> array = new ArrayList<ArrayList<Integer>>(); //the table
    		HashSet<Integer> n = new HashSet<Integer>(); //list of distinct products
    		int k;
    		
    		for (int i = 0; i<e; i++) {
    			k=i+1;
    			array.add( new ArrayList<Integer>() );
    			System.out.println();
    			for (int j = 0; j<a; j++) {
    				array.get( array.size() -1 ).add((k)*(j+1));
    				System.out.printf("%- 10d", array.get(i).get(j)); //print times table
    			}
    		}
    
    		int j;
    		for (int i = 0; i<e; i++) {
    			for (j = 0; j<a; j++) {
    				if (!find(array.get(i).get(j), n)) {
    						n.add(array.get(i).get(j));
    				}
    			}
    		}
    		
    		System.out.println("\n\nDistinct Products: "+ n.size());
    
    
    		}
    
    
    
    	public static boolean find(int q, HashSet<Integer> v) {
    	
    		return v.contains(q);
    	}
    }
    
  3. matthew said

    If we rearrange the loop a little, we can progressively generate the counts for all tables up to n:

    #include <vector>
    #include <stdlib.h>
    #include <stdio.h>
    int main(int argc, char *argv[])
    {
    int n = atoi(argv[1]);
    std::vector<bool> seen(n*n+1);
    int count = 0;
    for (int i = 1; i <= n; i++) {
    for (int j = i; j <= i*i; j+=i) {
    count += !seen[j];
    seen[j] = true;
    }
    printf("%d %d\n", i, count);
    }
    }

    $ ./timescount 9
    1 1
    2 3
    3 6
    4 9
    5 14
    6 18
    7 25
    8 30
    9 36
    
  4. matthew said

    That code should be:

    #include <vector>
    #include <stdlib.h>
    #include <stdio.h>
    int main(int argc, char *argv[])
    {
       int n = atoi(argv[1]);
       std::vector<bool> seen(n*n+1);
       int count = 0;
       for (int i = 1; i <= n; i++) {
          for (int j = i; j <= i*i; j+=i) {
             count += !seen[j];
             seen[j] = true;
          }
          printf("%d %d\n", i, count);
       }
    }
    
  5. ScottW said

    Pigeon Hole Principle

    import java.util.ArrayList;

    public class DistinctProductsForTimesTables {

    public static void main(String[] args){
    ArrayList distinctProducts = getDistinctProducts(1000);
    System.out.println(distinctProducts);
    }

    public static ArrayList getDistinctProducts(int N){
    boolean[] pigeonHole = new boolean[N*N+1];
    ArrayList distinctProducts = new ArrayList();

    for(int i=1;i<=N;i++){
    for(int j=i;j<=N;j++){
    pigeonHole[i*j] = true;
    }
    }
    for(int i=0;i<=N*N;i++){
    if(pigeonHole[i]){
    distinctProducts.add(new Integer(i));
    }
    }
    return distinctProducts;
    }
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 629 other followers

%d bloggers like this: