ashish_vaghani's blog

Scaler Apex problem
By ashish_vaghani, 4 years ago, In English

Given an integer $$$N$$$. Find two integers such that their product is strictly greater than $$$N$$$ and sum is minimum. How to solve this in O(1)?

P.S.- I posted this before, as I though contest ended at 9 pm. Sorry about that. JEEADVANCED can you confirm if the contest has ended.

  • Vote: I like it
  • -15
  • Vote: I do not like it

Comments Comments (16)
| Write comment?
»
4 years ago, # |
  Vote: I like it -16 Vote: I do not like it

2*sqrt(N)+1 are you really a specialist or is it magic?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Derivation/Logic of the above formula?
    Yes I am a specialist and I too get stuck at simple problems. There's nothing harm in that buddy :)

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 3   Vote: I like it +3 Vote: I do not like it

      Ya buddy did not mean to insinuate From Wiki

      • (a+b)/2 >= sqrt(x*y)
      • (a+b) >= 2*sqrt(x*y)
      • so a+b is 1+2*sqrt(x*y)
      → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      By the AM-GM inequality, we know that $$$a + b >= 2\sqrt{ab} >= 2 \sqrt{N}$$$. I assume that $$$a + b \in Z$$$. If so, when $$$N$$$ is a perfect square, we can achieve $$$2\sqrt{N}$$$ with $$$a = b = \sqrt{N}$$$. If $$$N$$$ is not a perfect square, we can achieve $$$2\sqrt{N} + 1$$$ with $$$a = b$$$ as the ceiling of $$$\sqrt{N}$$$ (and if it is possible, also consider (a, b — 1)).

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Like you said, For $$$N$$$ = 5, your answer is $$$(3, 4)$$$ whereas the optimal answer is $$$(2, 3)$$$

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          My answer for $$$N = 5$$$ is $$$(2,3)$$$. o_O

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Bruh. I knew you'd change that to floor of $$$sqrt(N)$$$. Now try for $$$N$$$ = 6, your answer is $$$(2, 3)$$$ whereas the right answer is $$$(3, 3)$$$ or $$$(4, 2)$$$ lol.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Oh I didn't read strictly greater. Then replace N with N + 1

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                4 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                That still yields $$$(2, 3)$$$ for $$$N = 6$$$ by your definition.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years ago, # ^ |
                  ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                  It does not. The ceiling of sqrt(7) is 3. So it produces whichever is better: (3,4) or (3,3).

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Why are u so indecisive and changed your comment to justify your point? -_-

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  I did change my answer; however, before it used to say (3,4) for 6, not (2,3). I

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  You're still indecisive.

                  The ceiling of sqrt(7) is 3. So it produces whichever is better: (3,4) or (3,3).

                  Go ahead and change your comment to $$$(3, 3)$$$, $$$(3, 2)$$$, according to your definition.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  ok whatever you know what I mean

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years ago, # ^ |
                  ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                  All i know you're stub and still wrong lol.

                  Have fun editing your comment ;)

                  PS: Don't downvote my comment out of shame lol.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years ago, # ^ |
                  ← Rev. 5   Vote: I like it 0 Vote: I do not like it

                  Yeah I was wrong (I never said I was right, and I'm grateful you pointed it out). The fix is pretty easy, though, just let $$$a$$$ be the floor of the square root of $$$n + 1$$$ and chose the best of $$$(a,a+1)$$$, $$$(a,a)$$$, and $$$(a + 1, a + 1)$$$.

                  → Reply