CODEWITHSUNDEEP
algorithmmath
weakwire
weakwire

Reputation: 9300

Detecting if an integer can be writen as a multiply of given integers

I have a set of given integers:

A[] = { 2, 3, 4, 5, 6, 7, 8, 10, 15, 20, 25, 30, 40, 50, 100, 500 }

  1. I want to check if a given integer T can be written as a multiple of the numbers in A[]; EDIT CLARIFICATION: any number in A[] can be used.If used can be used only one time. EX 60 is a valid T.60=30*2. AlSO 90 is valid . 90=3*5*6

  2. Check which numbers can form that integer T.

  3. Also return the 2 closest integers to the given T (that can be written that way) if the number T cannot be written as a multiple of that numbers.

Parts 2 and 3, I think I can sort out of my own if someone helps me with part 1.

I know this is an algorithmic question or even a mathematical one but if anyone can help, please do.

NOT HOMEWORK. SEE COMMENT BELOW.

#

SOLUTION. TY VERY MUCH FOR ALL ANSWERS.1 answer particulary (but the author choose to remove it and i don't know really why since it was correct.) Ty author (don't remember your name.)

#

Solution Code with a twist(The author's algorithm used multiple times one multiplier.This one uses multiplier only 1 time)

int oldT = 0;
        HashMap<Integer, Boolean> used = new HashMap<Integer, Boolean>();
        while (T != 1 && T != -1) {
            oldT = T;
            for (int multiple : A) {
                if (!used.containsKey(multiple)) {
                    if (T % multiple == 0) {
                        T = T / multiple;
                        used.put(multiple, true); 
                    }
                }
            }
            if (oldT == T)
                return false;
        }
        return true;

Upvotes: 5

Views: 290

Answers (2)

Nikita Rybak
Nikita Rybak

Reputation: 68016

If T is not very big (say, < 10^7), this is straight DP.

a[1] = true; // means that number '1' can be achieved with no multipliers
for (every multiplier x) {
   for (int i = T; i > 0; --i) {
      if (a[i] and (i * x <= T)) {
          // if 'i' can be achieved and 'x' is a valid multiplier,
          // then 'i * x' can be achieved too
          a[i * x] = true;
      }
   }
}

That's assuming every multiplier can be used only once.
Now, you can find decomposition of T if you have another array b[i] storing which multiplier was used to achieve i.

There's a lot of online content to get familiar with dynamic programming, if you have little time. It should give you idea how to approach such problems. For example, this one seems not bad
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg

Upvotes: 3

Rex Kerr
Rex Kerr

Reputation: 167901

I'm not sure exactly what you're asking.

If the user can select n*(one of those numbers), then note that you have the primes 2, 3, 5, and 7, so if your number is divisible by 2, 3, 5, or 7, then divide that out, and then you have n*(that one).

If you have to multiply the numbers by each other, but can do so multiple times, then note again that all of your numbers factor into powers of 2, 3, 5, and 7. Check if a bet is divisible only by these (divide each out until you can't divide out any more, then see if you're left with 1) and count the number of times you've divided by each one.

If you have to multiply the numbers by each other without replacement, then again find the prime factorization and remove from the list whichever number makes the powers present the most even. If you manage to remove all the multiples, you're done.

In all but the last case, the numbers that can be bet is very dense, so you can find the nearest just by going up or down and checking again. In the last case, searching for something near could be kind of tricky; you might just want to form a table of possible (low) bets and suggest something from that, assuming that users aren't going to bet 2*3*4*5*6*7*8*10*15*....

Upvotes: 1

Related Questions