Solving a multi variable polynomial

Question

For this equation, I need to count possible solutions:

$$ a + b^2 + c^3 + d^4 \le S $$

$$0\le a,b,c,d \le S$$

I tried the following approach:

       Integer S=Integer.parseInt(br.readLine());
      // get maximum possible value of a,b,c,d which satisfy equation
         int a=S;
        int b=(int) Math.sqrt(a);
        int d=(int) Math.sqrt(b);
        int c=(int) Math.cbrt(a);
        int count=0;
        for (int i = 0; i <= a; i++) {
            for (int j = 0; j <= b; j++) {
                for (int k = 0; k <= c; k++) {
                    for (int l = 0; l <= d; l++) {
                       int total=i+j*j+(int)Math.pow(k, 3)+ 
  (int)Math.pow(l,4);
                        if(total<=a) {
                            count++;
                        }
                    }
                }
            }
        }
          System.out.println(count);

Time complexity: \$O(n \times \sqrt{n} \times \sqrt[3]{n} \times \sqrt[4]{n})\$ (Not sure)

For large value, this takes time. Can someone please help me with better solution with time complexity?

Are a,b,c,d elements of the natural numbers ? Can they be negative, or even complex? Please update the problem statement :) — Rob Audenaerde
– Rob Audenaerde, Commented Jan 15, 2019 at 8:35
I have rolled back you last edit. Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. — Heslacher
– Heslacher, Commented Jan 16, 2019 at 6:39

Peter Taylor · Accepted Answer · 2019-01-16 08:43:20Z

a + b^2 + c^3 + d^4 <= S
For above equation ,I need to count possible solutions.

I tried following approach.
Integer inp=Integer.parseInt(br.readLine());
      // get maximum possible value of b,c,d which satisfy equation
      int b=(int) Math.sqrt(inp);
        int d=(int) Math.sqrt(b);
        int c=(int) Math.cbrt(inp);
        int count=0;
...

If I were the interviewer, I would already have marked you down heavily for your choice of variable names. The problem statement defines a, b, c, d, S. The natural choice of variable names for those values are a, b, c, d, S. Using b, c, d for something else almost looks as though you were deliberately trying to make the code unmaintainable.

                        if(total<=inp) {
                            count++;
                        }

Enumerating items one by one is nearly always the wrong way to count something.

If I asked you to count solutions to \$a \le S\$ would you write a loop? I hope not, because you can do it without any loop or any mathematical operations.

Now, how about \$a + b^2 \le S\$? This can be done with one mathematical expression. Hint: start from $$\sum_{b=0}^{\sqrt{S}} \textrm{countA}(S - b^2)$$

Cubes already grow quite fast, so

for (int c = 0; c <= maxC; c++) {
    for (int d = 0; d <= maxD; d++) {
        count += countAB(S - c*c*c - d*d*d*d)
    }
}

would be reasonably efficient. If you really want to microoptimise you can eliminate the multiplications in favour of some accumulators and addition, but that's probably not necessary for an interview question. They might ask about it in a follow-up.

What I understood is using all combination of a,b we can get possible count of solution for a,b variable & for c,d loop can be used. Both count can be multiplied. Solutions for a<=S = S+1 , ` Solution for b <= \sqrt (S-a) ` So for ex S=2 , we have countAB= (S+1) \times \sqrt(S-a)= 3*2 =6 but here solution (a,b) (2,1) is included which do not satisfy equation. Or did I got it wrong ? Also can you please briefly explain why following code is wrong to count something ? ` if(total<=S) { count++; }` — user3857802
– user3857802, Commented Jan 16, 2019 at 6:52

Stack Exchange Network

Solving a multi variable polynomial

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Solving a multi variable polynomial

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions