Geek Answers Handbook

Detection if an integer can be written as the multiplicity 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 }

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

  • Check which numbers can form this integer T.

  • Also return the 2 closest integers to the specified one T(which can be written this way) if the number Tcannot be written as a multiple of these numbers.

Parts 2 and 3, I think I can figure it out if someone helps me with part 1.

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

DO NOT CONGRATULATE. CM. COMMENT BELOW.

#

DECISION. VERY VERY FOR ALL ANSWERS .1 answer especially (but the author decided to delete it, and I don’t know why, because it was right.) Ty author (do not remember your name.)

#

Solution code with a twist (the author’s algorithm used one factor several times. This one uses the 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;
+5
source share
2 answers

If T is not very large (say, <10 ^ 7), this is a direct 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;
      }
   }
}

, .
T, b [i], i.

-, , . , . , . http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg

+3

, .

n * ( ), , 2, 3, 5 7, , 2, 3, 5 7, , n * ().

, , , 2, 3, 5 7. , ( , , , 1) , .

, , . , .

, , , , , , . - ; () - , , 2 * 3 * 4 * 5 * 6 * 7 * 8 * 10 * 15 *....

+1

More articles:


All Articles