Counting Series

You are given longs a, b, c and d. The numbers a and b define an arithmetic progression that consists of all numbers of the form a + b*x, where x is a nonnegative integer. Likewise, c and d define a geometric progression that consists of all the numbers that are equal to c * d^y, where y is a nonnegative integer. You are also given a long upperBound. Return the total number of integers between 1 and upperBound, inclusive, that belong to the arithmetic progression, the geometric progression or both.

Examples
1) 1 1 1 2 1000 = >1000

The arithmetic progression is: 1, 2, 3, 4, … .

The geometric progression is: 1, 2, 4, 8, 16, … .

Each positive integer is contained in at least one of the progressions.

2) 3 3 1 2 1000 => 343

This time, the arithmetic progression is: 3, 6, 9, 12, … .

The geometric progression is still: 1, 2, 4, 8, 16, ….

There are 333 multiples of 3 between 1 and 1000, inclusive, and there are 10 powers of 2, 512 being the highest. As these two progressions do not have any common elements, the total result is 343.

3) 40 77 40 100000 40 => 1

4) 452 24 4 5 600 => 10

The 10 numbers are: 4, 20, 100, 452, 476, 500, 524, 548, 572 and 596.

5) 234 24 377 1 10000 = > 408

import java.util.*;

public class CountingSeries {
    public long countThem(long a, long b, long c, long d, long upperBound) {
        Set<Long> geom = new HashSet<Long>();
        if (d == 1) {
            if (c <= upperBound) geom.add(c);
        } else {
            for (long x = c; x <= upperBound; x *= d) geom.add(x);
            }
        long res = 0;
        if (a <= upperBound) res += (upperBound - a) / b + 1;
        for (long x : geom) {
            if (x < a || (x - a) % b != 0)     ++res;   
        }   
        return res;  
    }  
    public static void main(String[] args) {   
        CountingSeries ct = new CountingSeries();   
        System.out.println(ct.countThem(1,1, 1, 2,1000));  
        System.out.println(ct.countThem(3,3, 1, 2,1000));   
        System.out.println(ct.countThem(40,77,40,100000,40));   
        System.out.println(ct.countThem(452,24,4,5,600));   
        System.out.println(ct.countThem(234,24,377, 1, 10000));  
    } 
}
Advertisement

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 )

Connecting to %s

%d bloggers like this: