Databases
StackOverflow2013
Postsdbo
POTwo factors whose product equals the number and their sum is minimum
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POTwo factors whose product equals the number and their sum is minimum
    primarykey
    data
    text
    <p>I am having trouble solving an optimization problem efficiently. I tried brute force but it did not work because I am attempting to solve this issue for large numbers.</p> <p>I am have trouble finding two factors of a given number such that its sum is minimum and the product equals the given number.</p> <p>Example input:</p> <p>For <code>110</code> the expected output is <code>10,11</code> since <code>10*11=110</code> and <code>10+11=21</code> which is the minimum. for <code>17</code> the expected output is <code>1,17</code> since <code>1*17</code> is the right answer.</p> <p>What efficient algorithms should I look into?</p> <p>Sorry but I forgot to mention that factors must be integers only.</p> <p>Here is my current attempt in Java:</p> <pre><code>import java.math.BigDecimal; import java.math.BigInteger; class fact1000 { public static void main(String args[]) throws Exception { BigInteger fact, a, b, result[] = new BigInteger[1001]; result[0] = new BigInteger("1"); /*computing all factorials till 1000 * */ fact = result[0]; for (int j = 1; j &lt;= 1000; j++) { fact = fact.multiply(new BigInteger("" + j)); result[j] = fact; } BigInteger bi=result[20]; //The Number i.e 100 fact BigDecimal bd = new BigDecimal(bi.toString()); String sqrt = sqrt(bd).toString(); BigInteger one = new BigInteger("1"); a = new BigInteger(sqrt.substring(0, sqrt.indexOf("."))); b = a; BigInteger prod = new BigInteger(a.multiply(b).toString()); long count = 0; System.out.println("Number = "+bi); while (prod.compareTo(bi) != 0) { count++; /* This is the block where I need help */ { if(prod.compareTo(bi)&lt;0) a=a.add(one); else b=b.subtract(one); prod = a.multiply(b); } /* * just to check the status after 1000000 counts */ if (count % 1000000 == 0) { System.out.println(count); System.out.println("diff " + bi.subtract(prod)); System.out.println("A " + a); System.out.println("B " + b); } } System.out.println(a); System.out.println(b); System.out.println(count); } /* * Function to find the sqrt of BigDecimal numbers */ public static BigDecimal sqrt(BigDecimal d) { int firsttime = 0; BigDecimal myNumber = d; BigDecimal one = new BigDecimal("1"); BigDecimal two = new BigDecimal("2"); BigDecimal epsilon = new BigDecimal("0.0000000001"); BigDecimal nByg = myNumber.divide(one, 9, BigDecimal.ROUND_FLOOR); BigDecimal nBygPlusg = nByg.add(one); BigDecimal nBygPlusgHalf = nBygPlusg.divide(two, 9, BigDecimal.ROUND_FLOOR); BigDecimal root = nBygPlusgHalf; firsttime = 99; do { one = nBygPlusgHalf; nByg = myNumber.divide(one, 9, BigDecimal.ROUND_FLOOR); nBygPlusg = nByg.add(one); nBygPlusgHalf = nBygPlusg.divide(two, 9, BigDecimal.ROUND_FLOOR); BigDecimal savegdiff = root.subtract(nBygPlusgHalf); if (savegdiff.compareTo(epsilon) == -1) { firsttime = 0; } else { root = nBygPlusgHalf; } } while (firsttime &gt; 1); return root; } } </code></pre>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. UScoding
    1. UScoding
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POTwo factors whose product equals the number and their sum is minimum
      1. This table or related slice is empty.
      1. VTDownMod
    2. VO
      singulars
      1. POTwo factors whose product equals the number and their sum is minimum
      1. This table or related slice is empty.
      1. VTDownMod
    3. VO
      singulars
      1. POTwo factors whose product equals the number and their sum is minimum
      1. This table or related slice is empty.
      1. VTDownMod
    1. COpost what you have tried.. sounds like homework
      singulars
      1. POTwo factors whose product equals the number and their sum is minimum
      1. USstinepike
    2. CO*So please suggest me some efficient algorithm.* What have you tried? Or are you expecting us to solve your problem?
      singulars
      1. POTwo factors whose product equals the number and their sum is minimum
      1. USLuiggi Mendoza
    3. COIf you can wrap your head around the math, you can do it in java.
      singulars
      1. POTwo factors whose product equals the number and their sum is minimum
      1. USNicolás Carlo
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload