Can /g/ code basic problems?

>failing on trivial problems
just use stack overflow

File: CjkCd25UYAAiEHQ.png (185KB, 600x450px) Image search: [Google]

185KB, 600x450px

>>56165296
>do my homework for me pls

>>56165296
Three minutes later :

#include <stdio.h>
#include <stdlib.h>

int isPerfect(int input){

        for(int i = input; i > 0;i--)
                if(input % i == 0)
                        if(input / i == i)
                                return 1;       

        return 0;
}

int main(int argc, char* argv[]){

        int input = 0;

        printf("input : ");
        scanf("%d", &input);
        printf("\n");

        if(isPerfect(input))
                printf("Perfect !\n");
        else
                printf("NOT perfect !\n");

        return 0;
}

Here's your fucking homework

>>56165387
He said no brute-force comparisons. That's not even the efficient way to go, faggot. You start from 1 to input/2 when verifying.

>>56165371
It's an interview question you retard, and a pretty common one at that.

I'm not even a CS major nor am I in school at the moment.
>b-but memes.

>>56165417
shit skipped that line

>>56165417
Because checking numbers inbetween input and input/2 is retarded and redundant(for input>1), forgot to add.

/** C Program to check Perfect Square **/

#include <stdio.h>

int main()
{
    int a, n;
    printf("Enter a number: ");
    scanf("%d", &n);
    for(a = 0; a <= n; a++)
    {
        if (n == a * a)
        {
            printf("YES");
            return 0;
        }
    }
    printf("NO");
    return 0;
}

>>56165422
>>56165371
I googled the answer. I have a masters degree in CS. The solution using Hensel's Lemma is not a basic interview question/homework, you faggots.

>>56165296
damn im bored

less o d d n u m b e r s

literally 10 seconds

>>56165508
it's nothing crazy as far as big four interviews go.

you have a masters in CS and gave up that quick?

function isSqrt(x) {
     return Math.round(Math.sqrt(x)) ** 2 == x;
}

>Efficient solutions don't count

>>56165571
what does this even mean anon

>>56165296
Your first mistake is thinking anyone in here will give you an honest answer about their coding experience, logic solving skills or general intelligence.

The time it took you does not matter unless you're under certain contractual time constraints or some malady that is greatly reducing your life span.

What matters is you learn from it. Go fucking learn.

>>56165597
well shit anon this isn't that binary, if you have some impressive tricks that involve a little guessing feel free to post it.

File: 1445572805780.gif (115KB, 500x700px) Image search: [Google]

115KB, 500x700px

>>56165636
I already figured out the solution and I did learn anon.

I just thought it was a very interesting problem that some people on /g/ may enjoy. It's good practice and i'm curious to see the extent of difficulties that people have on here.

We've fucking had enough fizz buzz memes, get coding faggots.

template<typename T>
bool issquare(T v) { return false; }
bool issquare(square v) { return true; }

>>56165495
this is my solution too, as a CS undergrad. is this not the solution??? you can use some conditions to prevent checking really low numbers for really large numbers, though obviously that breaks down eventually for very high values.

maybe it should try squaring n/2, then n/4, then n/8 till it gets a value <n, then work up?

>>56165738
>>56165571
>>56165573

What an elegant, intuitive and intelligent solution. Stop being smartasses on the internet.

private final static boolean isPerfectSquare(long n)
{
  if (n < 0)
    return false;

  switch((int)(n & 0x3F))
  {
  case 0x00: case 0x01: case 0x04: case 0x09: case 0x10: case 0x11:
  case 0x19: case 0x21: case 0x24: case 0x29: case 0x31: case 0x39:
    long sqrt;
    if(n < 410881L)
    {
      //John Carmack hack, converted to Java.
      // See: http://www.codemaestro.com/reviews/9
      int i;
      float x2, y;

      x2 = n * 0.5F;
      y  = n;
      i  = Float.floatToRawIntBits(y);
      i  = 0x5f3759df - ( i >> 1 );
      y  = Float.intBitsToFloat(i);
      y  = y * ( 1.5F - ( x2 * y * y ) );

      sqrt = (long)(1.0F/y);
    }
    else
    {
      //Carmack hack gives incorrect answer for n >= 410881.
      sqrt = (long)Math.sqrt(n);
    }
    return sqrt*sqrt == n;

  default:
    return false;
  }
}

>>56165790
No it's not. It's literally calculating all square roots until whoopty fuckin' doo you have a match.
In a real interview they would eventually steer you towards what the correct answers look like because it's trivial to just do monkey guessing even if you do some chopping off at parts

There is a VERY elegant and distinct solution to the problem. Might even be several. When you get the answer you'll know it right away.

>>56165876
Post it then, you dumb asshole.

>>56165896
he's probably talking about binary searching the actual root, given some decimal point you take out off your ass. Or just generating all the squares and checking (i from 1 to whatever, i+=2, s+=i if input==s, 1, input<s, 0)

>>56165296
big-ol precomputed table.

Probably a RLE encoded thing would work well.

>>56165495
You could change (a <= n) to (a*a <=n)

>>56165896
Yeah fuck no. It's interview time faggots. If you can't figure it out too bad.

Learn to spot regularities. That should be the first thing that comes to one's mind if you have any mathematical competence and look at this type of problem. Or you could learn to google.

>>56165977
You're clearly talking about the odd number adding up solution then. Calculate your execution time you fag, is this an interview for IT manager at burger king?

>>56165923
it has nothing to do with caching or having some kind of buffer or table to refer to. Jesus fuck you guys would have people laugh at you in the competitive interviews.

It's just about one level above having if statements for every number in fizz buzz.

>>56166024
You either cannot properly read comments, don't have basic understanding of the english language or are trolling.

>>56165977
so you don't know what you're talking about, got it.

I thought about it a little bit more, should I use newton's method? if i do enough iterations i should get very close to the answer, then i can check the nearest integer and see if it's a match.

you can tune the number of iterations to get speedier results that are less accurate, or vice versa?

1 + 3 + ... + (2n-1) = n^2

Would be another way to do it. Still bruteforce though...

>>56166012
You can do the same type of filtering/optimizing for the odd number summation too. Or are you too stupid to realize this?

That's the entire fucking point, the trick is to find the route without any type of guessing or bullfuckery, the point isn't necessarily execution time faggots.

But yes, the odd number summation is the answer expected in almost every interview they ask this question.

>>56166074
i thought about it even more and this won't work well for bigger numbers.

Why aren't you allowed to use ^0.5 when it is the simplest manner to test?
Just because it is?

>>56166115

O(sqrt(n)) for the summation. Checking if i*i==input from 1 till i*i>n is O(sqrt(n)). Why is your solution better?

static bool IsSquare(int n)
{
    int i = 1;
    while(true)
    {
        if (n < 0)
            return false;
        if (n == 0)
            return true;
        n -= i;
        i += 2;
    }
}

C# here, enjoy.

>>56166185
Oh I just actually read the OP properly.

It's one of those bullshit ones.

Never mind.

>>56165495
>number 9
>NONONOYESNONONONONONO

>>56165495
This.
My solution in case anyone is interested
<code>
bool isPerfectSquare(int n){
for(int i=1;;i++)
if(i*i >= n)
return 0;
else if(i*i==n)
return 1;
}

>>56166210
give me a break

>>56166012
you mean this?
9-4=5
16-9=7
25-16=9
36-25=11
49-36=13

I don't see an algorithm to exploit this regularity

>>56166277
I think he means that
1+3=4
1+3+5=9
1+3+5+7=16
if n is the number of odd numbers than it is n^2

>>56165296
https://en.wikipedia.org/wiki/Newton%27s_method

>>56166277
this >>56166076

What's the rationale for NOT bruteforcing it?

>>56166338
maximum meme points

>>56166210
How are you this fucking braindead? 0 1 2 3, retard.

first time trying to use code tags

#include <iostream>

using namespace std;

int num=0,mitad=0,raiz=0;
bool sqr=false;

int main()
{
    cout << "Digite el numero a evaluar\n";
    cin >> num;
    mitad = (num/2);
    for (int i=0; i<mitad; i++)
    {
        if((i*i)==num)
        {
            sqr=true;
            raiz=i;
        }
    }
    if (sqr)
    {
        cout << "\nEl numero tiene raiz cuadrada. la cual es " << raiz;
    }
    else
    {
        cout << "\nEl numero no tiene raiz cuadrada";
    }
    return 0;
}

its in spanish but you should understand


>tell me why my code sucks /g/

>>56166167
again it's not necessarily about execution time. it's about recognizing the pattern of prime numbers and building a concrete check that is ENTIRELY composed of simple addition and an intuitive construction.

in the I*I check you are directly wasting loop cycles to just ramp up to the number range necessary. It's NOT the intuitive solution at all, I guarantee in an interview this is the answer they hear the most and they will not take it positively that you can do simple if statements until shit matches.

Also I don't think it's faster on average. I tried in leetcode (which tries a bunch of different sample inputs) and the i*i solution didn't even compile in time for me (failed) while odd summations succeeded.

>>56166484
That is the intuitive way.

>>56166484
Here you go big boy https://en.wikipedia.org/wiki/Big_O_notation

Also if you're interviewing for firms that accept one trivial O(sqrtn) solution but don't accept another trivial solution with the same complexity, you're interviewing for the wrong firms.

#!/usr/bin/python3

def psq(n):
    if n == 1:
        return True

    if not n == round(n):
        return False
    n = int(n)
    
    for i in range(2, n):
        if n % i == 0:
            return psq(n / i**2)
    
    return False

x = int(input())
if psq(x):
    print('yes')
else:
    print('no')

how's this senpaitachi

File: 2016-08-19-185900_462x360_scrot.png (10KB, 462x360px)

10KB, 462x360px

>>56165296
im sorry senpai
took me 20 secs

perfect n = n `elem` map (^2) [1..n]

function st(n){var i,j;for(i=1,j=3;i<=n;i+=j,j+=2){if(i==n)return 1;}return 0;}

st(2500)
=> 1
st(2044)
=> 0

>>56166597
more efficient but excludes 1

perfect n = n `elem` map (^2) [1..div n 2]

>>56165296

would somebody explain this portion:

for(a = 0; a <= n; a++)
    

I'm having a hard time understanding what is happening here because I am dumb.

I understand it is a loop but I haven't thought about this stuff in a while, and I'm not sure what it is doing.

>>56166685
>>>/web-dev/

but srs

for a = 0, a <=n increase a by one
meaning that do the body of this for loop n+1 times
the boddy has access to the vars a and n of course

>>56166685
>n = 25 , a = 0 [0*0 != 25]
>n , a = 1 [1*1 != 25]
>n , a = 2 [2*2 != 25]
>n , a = 3 [3*3 != 25]
>n , a = 4 [4*4 != 25]
>n , a = 5 [5*5 == 25] {yes}

>>56166210
Are you retarded?

>>56166730
>>56166761


Oh I get it now.

The loop keeps going while a is <= n incrementing a by one, and then if n is = to a * a the result is true.

I see it now.

thanks dudes

>>56166685
it's a for loop, which has 4 parts.
1. Some variable(s) for the loop to work on.
2. A condition that has to be met for the loop to run.
3. An action to perform every time the loop is run.
4. The body, which is the "stuff" that gets done every go around of the loop.

So 1. is a=0, 2. is a <= n and 3 is a++, 4 isn't included but would go afterwards, in braces {}.

They're pretty simple but a=0 is just setting a variable, a <= n means "a less than or equal to n" and a++ means "add one to the variable a".

>>56166819

yeah it took me a bit with the logic and what the for loop was doing there.

i don't program (obviously). just a passing interest.

File: growing_squares.png (52KB, 500x408px) Image search: [Google]

52KB, 500x408px

>>56166548
>has no idea what the fuck embarrassingly parallel means or too retarded to know it's applicable in the odd summation method
>but I sent you the big O wiki!

>Also if you're interviewing for firms that accept one trivial O(sqrtn) solution but don't accept another trivial solution with the same complexity, you're interviewing for the wrong firms.
I never claimed this. The problem (and similar ones) are often directed towards pattern recognition because that type of thinking and resulting solution goes one step higher than what is essentially smashing numbers together until it works and wasting a fuck load of loop cycles unless you do some butchering and hard-coded guessing of the scope, but that can also be applied to the odd summation in the same way anyways so it's not a valid argument.

They want to hear the answer that shows a deeper understanding of how prime numbers relate and can be verified through pure induction and other discrete tricks, ideally.

>>56166318
>>56166322
thanks, is this a valid solution?

int perfect(int n) {
    int i = 1;
    int a = i;
    while (a < n) {
        i += 2;
        a += i;
    }
    return a == n;
}

>>56166484
this solution seems just as bad as the others.

>>56166900
how would this be implemented though? Do you still generate each square or I'm missing something?

You guys can try your code on this website. Supports a bunch of languages.
https://leetcode.com/problems/valid-perfect-square/

It will auto try a ton of sample inputs that leave no corner of logic untested and let you know if the code passes. If your code is also too slow it will fail the test too.

It took op 30 minutes to solve that problem but /g/ingers are arguing for 2h.

>>56167155
>sign in

nope

>30 minutes on a perfect square problem
are you clinically braindead

>>56167185
yeah I just noticed. sucks but the website is good, tons of great questions but a decent amount locked under the shill wall. The OP question is also rated as medium difficulty for anyone wondering (at least with odd summation solution)

>>56165806
copying code off wikipedia is cheating anon

Or you could do a dichotomy search. It's faster than brute forcing every possibility and it's applicable to floating points.

>>56167219
let's see the code anon
:)

>>56167359
pls show and/or explain anon, i'm interested

int checker = num^1/2
if checker != float {
return true;
}

>>56167444
A dichotomy search is choosing between to alternatives and progressively reducing the range of search. Say you're searching for the square root of 16. Your domain of search is between 2 and 16/2 = 8. You divide this domain in two equals parts, by dividing the highest+lowest extreme by two which gives you a number delimiting the two sub domains, in our case 4. Then you test this number, if it's higher than what you're supposed to get, your new domain is the delimiting number to the highest extreme. If its lower, your new domain is the delimiting number to the lowest extreme.
It can be applied to floating points because you get find a square root with some precision with it, and you can define the precision.

Heres an example in python, it's pretty straightforward.

def sqrt(n):
  low = 0
  high = n+1
  while high-low > 1:
    mid = (low+high) / 2
    if mid*mid <= n:
      low = mid
    else:
      high = mid
  return low

>>56167121
>how would this be implemented though? Do you still generate each square or I'm missing something?

Pretty sure odd summation is embarrassingly parallel because it's entirely deterministic, it's literally just a summation of all odd numbers. 0 guessing or wasted cycles/cpu time.
When an algorithm is deterministic, it's much easier to implement efficiently in a manner such that the CPU pipeline/cores are all being used simultaneously and not sitting idle.

maximum resource utilization is inherently more difficult when the algorithm is not deterministic. Correct me if i'm wrong, but i'm pretty sure this is how it goes down.

>>56166484

> I guarantee in an interview this is the answer they hear the most and they will not take it positively that you can do simple if statements until shit matches.

have you even done an interview question?? It's mostly "how do pointers work" and "find a thing inside another thing"

They're impressed with candidates who can answer anything other than "Potato", because you know what? Some candidates don't even get that far.

>>56167873
Anon you must have interviewed at some shit companies or just for intern positions. Some companies are definitely selective, and it's in their best monetary interest to be.

Big four will really push your shit in most interviews. Constant white-boarding interview after interview for almost a day.
Not sure where you live but in my area (NYC), their is definitely talent too.
At the good companies the questions go beyond pointers and fizzbuzz and if you don't know your shit they will sniff you out like a dog.

>>56167652
This is slick as fuck. Going to try and internalize this shit.

Thanks anon.

what is /g/s favorite interview question so I may acquire more practice

File: 1433322937958.png (13KB, 426x364px)

13KB, 426x364px

>>56168198

#include <stdio.h>

void FizzBuzz()
{
    for (int i = 1; i <= 100; i++)
    {
        if (i % 15 == 0){
            printf("FizzBuzz\n");
        }
        else if (i % 5 == 0){
            printf("Buzz\n");
        }
        else if (i % 3 == 0){
            printf("Fizz\n");
        }
        else{
            printf("%d\n", i);
        }
    }

    return 0;
}

int main()
{
    FizzBuzz();

    return 0;
}

File: 1455480788977.jpg (12KB, 336x286px) Image search: [Google]

12KB, 336x286px

>>56168225

>>56165296
Is this one of this "Some dumb will do my homework" thread?

File: 1412973590450.jpg (264KB, 1024x768px) Image search: [Google]

264KB, 1024x768px

>chapter 1 of SICP
Still took me a while. I didn't remember the algorithm correctly. They even warn you:
> Consider an initial guess y1. [If] the next guess is y2 = x/y1 [then] the next guess is y3 = x/y2 = x/(x/y1) = y1. This results in an infinite loop in which the two guesses y1 and y2 repeat over and over, oscillating about the answer.
>One way to control such oscillations is to prevent the guesses from changing so much. Since the answer is always between our guess y and x/y, we can make a new guess that is not as far from y as x/y by averaging y with x/y, so that the next guess after y is (1/2)(y + x/y) instead of x/y.

>>56165296
You could do it in O(logn) with a binary search, but there may be some math wizardry that is more efficient

>>56168198
Invert a binary search tree in haskell

>>56169974
>You could do it in O(logn) with a binary search
Wouldn't that still be brute forcing?
Wouldn't anything involving a loop be a brute force?

>>56167967
>Some companies are definitely selective, and it's in their best monetary interest to be.

Depends on the job. The big companies have more vigorous interviews because they have a lot of applicants. They have the luxury of being very selective in who they hire.

>>56167652
That's still brute-forcing. OP wants an elegant solution.

>>56170324
If the OP is expecting a constant time complexity algorithm he's actually a dumbass. And so are you.

if(Math.sqrt(num)==(int)num

>>56169974
>but there may be some math wizardry that is more efficient
There can't be. The input contains O(log n) bits, and you need to read all of them, which means you need at least O(log n) time. (I should write an omega or theta here but I don't feel like copypasting those symbols from somewhere so fuck it.) Since binary search is O(log n), it is optimal for this problem.

>>56170324
You clearly haven't got a clue what "brute force" means. This isn't it.

>>56170521
>You clearly haven't got a clue what "brute force" means. This isn't it.

Why isn't it brute force? It does an exhaustive search for a solution. It's only slightly less retarded than going through every number.

>>56167967

Why do you care what company you work at? Google's 6 figs work just as well as bob's backyard consultancy's 6 figs.

>>56170557
>It does an exhaustive search for a solution.
No, it doesn't. "exhaustive search" is jargon for "going through every number", which as you say this algorithm does not do.

>>56170607

Using heuristics doesn't make the algorithm non-brute-force.

File: 1471630764397.jpg (110KB, 600x865px) Image search: [Google]

110KB, 600x865px

Can /g/ write a program that will find me a gf?

>>56170642
Neither "heuristics" nor "brute force" mean what you think it means. Please stop using terms you don't understand.

File: math.png (64KB, 1720x570px) Image search: [Google]

64KB, 1720x570px

This explains the answer for anyone still wondering.
Basically you just check if the number is part of the summation. It's a discrete mathematics trick which can be proved through induction.

It's a discrete process and 0 wasted cpu cycles (not bruteforced).

>>56170669
tell me that leads to a picset or a video.

Just implement a shitty version of sqrt using the Babylonian method.

>>56170568
You want to be around people who are actually better than you so you can continue to improve at whatever the job is. Looking exclusively at the immediate salary is naive.

If you're working with a bunch of retards you will learn much more slowly and you won't be maximizing opportunity cost.

>>56170711
This solution is O(sqrt(n)) while an O(log n) solution exists. Do you honestly think that a slow solution is somehow better than faster solutions because none of the intermediary results have any clear meaning? Because that's what your retarded intuition of "brute force" seems to amount to.

>>56165432
should also check is ebin a square first before starting the factorial part. If you're optimizing.

>>56170763
post code please of your solution

The summation check can be implemented with about 3 lines of code and just about maximizes hardware utilization because of the discrete nature. that's what makes it so appealing.

inp = int(input("enter number: "))
x = 2
ans = ""
while x < inp:
    if x*x == inp:
        ans = "yes"
        break
    else:
        ans = "no"
    x += 1
print(ans)

>>56170809
it's basic binary search

>>56170607
I'm afraid it is still a brute force.

It takes n(+1) as the highest bound, sets the lowest bound to 0 then loops through a loop adjusting the bounds until the square root is found.

>>56170984
Bruteforcing.

>>56169999
>interview question

>>56170984
multi-threaded odd number theorem will be still be much faster than multi-threaded binary searches.
should be possible to have a GPU be used very efficiently just by running parallel summation checks with no stalling in any scenario ever, no best case/worst case/average. so it's also possible to predict the exact time it will take to solve x because of the discrete nature.

>op question has literally nothing mentioned about any bruteforce or any misconception of thereof
>entire thread consists of some faggot claiming only his obscure method is the solution
No wonder you're still doing interviews, faggot. :^)

>>56165296
>>56165417
>>56166076
>>56170233
>>56170324
>>56170521
>>56170557
>>56170642
>>56170673
>>56170711
>>56170763
>>56171018
>>56171028
There's no solution, because everything is brute force

>>56165296

issquare :: Int -> Bool
issquare n = n `elem` takeWhile (<=n) squares
    where squares = map (^2) [1..]

>All these arguments about time complexity
The most practical answer would be to generate a large list of perfect squares use a hashtable for dank O(1) performance. Apparently space complexity isn't important.

>>56166434
>non english
kek

>>56171690
>generating a large list is free

>>56171648
And for all you autists arguing about brute force, this one is "brute force" but only took about half a second for an input of One hundred thousand billion

>>56165296

λ import Math.NumberTheory.Powers
λ let isSquare n = n == integerSquareRoot n ^ 2
λ isSquare 16
True
λ isSquare 14
False
λ 

wow so hard

File: 1471231890313.png (209KB, 3757x2411px) Image search: [Google]

209KB, 3757x2411px

>>56171800

>>56171648
Most complete answer desu

File: 1471226693246.jpg (220KB, 1464x762px) Image search: [Google]

220KB, 1464x762px

>>56171836
Thank you anon

>>56171800
Oh, no built-in square root, so I have to spend a few extra lines implementing heron's algorithm

the horror

integerSquareRoot = heron n n
heron n a = go $ step a
    where step k = (k + n `quot` k) `quot` 2
          go k | m < k     = go m
               | otherwise = k
              where m = step k

>>56171787
>He doesnt already have a perfect square lookup table
100% free

>tfw had to google what a perfect square is

>>56171996
Me too, it's a stupid name, sounds like it's a subset of square numbers

Using Newton Raphson works rather well.

isSquare :: Double -> Bool
isSquare n = nearInteger (nrSqrt n) 0.000001

nrSqrt :: Double -> Double
nrSqrt n = within 0.00001 (approximations init n)
  where init = n / 2

approximations :: Double -> Double -> [Double]
approximations x0 n = myIterate (next n) x0

next :: Double -> Double -> Double
next n x0 = (x0 + n / x0) / 2

within :: Double -> [Double] -> Double
within eps (x0:t@(x1:xs)) = if myAbs(x0 - x1) < eps then x1 else within eps t

myIterate :: (a -> a) -> a -> [a]
myIterate f x = x : iterate f (f x)

myAbs :: (Num a) => a -> a
myAbs n = (signum n) * n

nearInteger :: Double -> Double -> Bool
nearInteger n eps
    | n - j > 0 = n - j - eps <= 0
    | n - j < 0 = n - j + eps >= 0
    | otherwise = True
    where
        j = fromInteger (round n) :: Double

>>56165296
>Retard brute-forcing comparisons don't count and neither do functions like ^(1/2) or any other cheap tricks.
Hard mode: You may only assign constant values to variables, add, or check for inequality conditions.

Hint:
[spoiler]If n^2 is a perfect square,

n^2 + 2n + 1

is also a perfect square. So is

n^2 - 2n + 1

.[/spoiler]

>>56171648

let f n = foldr (\x y -> x == n || x < n && y ) False $ scanl (+) 0 [1,3..]

>no brute force
Is this math class or a CS class?
Seems more like the kind of stuff you'd do in number theory.

(define (perfect n)
        (define (helper psum prev n)
                (cond ((= psum n) #t)
                      ((> psum n) #f)
                      (else (helper (+ psum (+ prev 2)) (+ prev 2) n))))
        (helper 1 1 n))

>>56172301
>Is this math class or a CS class?

you shouldn't code like a retard in any class?

def fuck(op):
    n = 1
    while True:
        if n * n == op:
            return True
        if n * n > op:
            return False
        n += 1

>>56172324
Well the non retarded coding would be to just use the library.
The coders of the library should know math and have an elegant solution.

>>56172324
In fact I'm not sure if this problem can avoid brute force entirely. It's like finding primes to some extent (see it's number theory m8), so the best thing is to find the most efficient brute force method.

>>56172345
Rewrite in Rust by same person.

fn fuck(op: u64) -> bool {
    let mut n: u64 = 1;
    let mut answer: u64;
    while true {
        answer = n * n
        if op == answer {
            return true;
        } else if answer > op {
            return false;
        }
    }
}

I would use binary search, 16 Iterations tops. Starting from the 2<<16(considering we use unsigned) I'd gradually lower it if its square is less than the number and 1<<i to the binary representation if it's less. Something like that, I'm on my phone now.

>>56166900
No, they don't. Fuck off, you're embarrassing yourself.

Source: I actually have a job.

>>56166145
Because it seems the main reason for this question is not to test if you can code since you aren't allowed to brute force it or use a standard library. It's to see if you took several math courses. If the job description didn't say that you need to be proficient in mathematics then they are looking for people that spent the last year only doing interview question problems

>>56172443
1<<16 but you got the idea

>>56171028
Binary search is not brute forcing you thick headed cunt. No wonder you don't have a job.

use std::env;

fn main() {
    println!("{}", fuck(env::args()
                                   .nth(1)
                                   .expect("Didn't get argument")
                                   .parse::<u64>()
                                   .expect("Parse error")));
}

fn fuck(op: u64) -> bool {
    let mut n: u64 = 1;
    let mut answer: u64;
    loop {
        answer = n * n;
        if answer == op {
            return true;
        } else if answer > op {
            return false;
        }
        n += 1;
    }
}

./PerfectSquare 1000000000000000000 runs in 512ms on my machine. Good luck guys

>>56171144
Worst case scenario for binary search is 16 comparisons, you'd waste more time on initializing the GPU.

>>56172518
The problem is to solve this in constant time, adding more sugar like binary search on top does not make it constant time.

>>56172573
Constant time can be way, way more than log(n). Especially considering binary search is, like, 9 lines long.

>>56167873
All big traditional companies that have been doing data since the 70s will check your CV, see if you know a few people in the company, ask which languages you have coded in and for how long to see if you match the job ad. If you aren't socially awkward you will probably get hired.

By now I know people at every big company in the city. If I want a new job I just call people up or they call me. No can the monkey dance faggotry.

But I do know that small startups and other hipster companies like Google expects you to do various tests, spend a few days working for free with the team so they can get a "feel" for you.

>>56172546
>.nth(1)
Did you just try to use the executable's name as input?

>>56165296
Binary search to find the square. O(logn). Wew

>>56172711
you would still need to populate the binary tree with "brute force"

and in that case you might as well use a hash map and just check if a lookup fails / succeeds to get O(1) lookup time

>>56172697
No. Mind your own business if you don't know how Rust works.

>>56172754
>binary search
>binary tree
Are you retarded?

>>56172754
Lol are you dumb. Only calculate the values you need, don't create a tree of all squares.

>>56172711
can u do an example in haskell?

Somebody fucking show him the binary search solution, phoneposting is pain.

>>56172759
What a shitty language. I bet it's popular with hipsters.

>>56172769
If you're going to make an array with values within which you will do a binary search, you might as well use a hashmap

>>56172838
>array with values
ARE YOU FUCKING RETARDED? You need 2 int numbers.

>>56172754
Brute force is trying every option without rhyme or reason. This way is clear, purposeful, and efficient. Also you don't need to create a datastructure, you just need division and a comparitor.

>>56165296
My solution in O(log(n)). Uses binary search basically.

bool perfectSquare(int input){
    if (input == 1) return true;
    if (input == 2) return true;

    int lower = 1;
    int upper = input;
    int middle;
    while(upper-lower > 1){
        middle = (int) (lower + upper)/2;
        if (middle*middle == input) return true;

        if(middle*middle>input){ //lower half
            upper = middle;
        }
        else{ //upper half
            lower = middle;
        }


    }
    return false;

}

>>56172864
Okay. I had assumed that doing multiple comparisons like >>56172855 was considered brute force as well.

use std::env;

fn main() {
    println!("{}", binary(env::args()
                                   .nth(1)
                                   .expect("Didn't get argument")
                                   .parse::<u64>()
                                   .expect("Parse error")));
}

fn binary(target: u64) -> bool {
    let mut low: u64 = 1;
    let mut high: u64 = 3037000499; // floor(sqrt(std::u64::MAX))
    let mut mid: u64;
    let mut answer: u64;
    let mut last_low: u64 = 0;
    let mut last_high: u64 = 0;

    while low <= high {
        if last_low == low && last_high == high {
            return false;
        }
        last_low = low;
        last_high = high;
        mid = (high + low)/2;
        answer = mid * mid;
        if answer == target {
            return true;
        } else if answer > target {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    false
}

Runs in 18ms with 1000000000000000000

>>56172874
Why did I make input == 2 returns true?
Am I retarded? Scrap that.

File: PaintDotNet_2016-08-20_11-15-28.png (3KB, 109x221px) Image search: [Google]

3KB, 109x221px

>>56165296
>>56165508
isSquare(n)
int a, b;
b = 0.5*n
for(int i = 0; i < 20; i++) b = (b+n/b)/2
return b*b == n

obviously could be made a lot better, but i'll leave it at that. sample run for n = 28493 pictured

What do you think of this?

#include <iostream>

bool issquare(const int &x) {
    int copy = x;
    while (copy % 2 == 0) {
        copy %= 2;
        if (copy == 0) {
            return true;
        }
    }
    return false;
}

int main() {
    int x = 5;
    int y = 8;
    std::cout << issquare(x) << std::endl;
    std::cout << issquare(y) << std::endl;
    std::cin.get();
    return 1;
}

File: triggered.jpg (16KB, 320x371px)

16KB, 320x371px

>>56166229
>if(i*i >= n)

>>56165296
the perfect squares are the partial sums of the series of odd integers.

>>56172951
Why are you returning 1 in main? And no it won't work. Try putting in 81.

>>56173072
I just realized that I made it in a stupid way - the "copy %= 2" makes no sense. This works:

#include <iostream>

template <typename T>
bool issquare(const T &x) {
    T tmp = 1;
    while (tmp <= x) {
        tmp *= 2;
        if (tmp == x) return true;
    }
    return false;
}

int main() {
    for (int i = -9; i != 1025; i++) {
        std::cout << i << "\t" << issquare(i) << std::endl;
        std::cin.get();
    }
    std::cin.get();
    return 1;
}

How should I treat negative numbers though?

>>56167239
even carmack copied that code man

>>56173087
>How should I treat negative numbers though?
>integer
Return false.

>>56165602
It means that if you add odd numbers you get perfect squares. Or at least I think that's what he meant.
Which is true.

>>56173087
Your program will always return failure in main.

>>56173087
This is a brute force solution. A very poor brute force solution that won't catch 9 as a perfect square.

>>56165387
>>56165495
>>56165575
>>56165742
>>56165806
>>56166185
>>56166434
>>56166593
>>56166597
>>56166597
>>56166643
>>56166643
>>56166648
>>56167077
>>56167652
>>56170373
>>56170889
>>56171648
>>56171800
>>56171869
>>56172019
>>56172261
>>56172318
>>56172874
>>56172951
>>56173087
Time your program with 1000000000000000000 so we can stop discussing.

Would making an array of perfect square roots and then checking if the number is in it count as brute forcing?

Oh who am I kidding, of course it is.

>>56173177
18ms with program >>56172892

>>56173177
>1000000000000000000
Only fits in a uint64. If you are going to be stupid use 18,446,744,073,709,551,615.

>>56173200
Got 18ms again.

>>56173213
The score not only depends on the efficiency of the code but also the speed of your CPU, which makes it a worthless comparison.

>>56173242
You can always recheck on a single machine if the scores are close. If you get one program that runs in 18ms and another one that runs in 1500s you can be fairly certain that the first one runs faster.

>>56173258
Or you could just use the big O notation to determine the runtime.

File: cb_console_runner_2016-08-20_11-56-59.png (24KB, 716x455px) Image search: [Google]

24KB, 716x455px

>>56173177
>not getting a negative runtime
bit slow there guys
in all seriousnes though, a good algorithm takes a lot less than 1000 cpu cycles(several hundred nanoseconds) so timing the whole process is pointless

>>56173242
Use Ideone

>>56173276
>every program that runs in O(log(n)) has the same runtime

>>56173280
check the post above yours

>>56165296
>not defining what a perfect square is
shit problem specification

>>56173177
Time your program with 10^1000000000000000000 or shut the fuck up

>>56173320
That's a big number

>>56173368
For your language

>>56173320
10^1000000 can be realistically done in under a second, but that's too big.

Mine, do not steal - 10 min

public string CheckIfPerfectSquare(int numberToCheck)
{
    bool isNumberEven = numberToCheck % 2 == 0;
    int maxNumberToCheck = numberToCheck/2;
    for(int i = 0; i <= maxNumberToCheck; i++)
    {
        if(isNumberEven && i % 2 != 0)
        {
            continue;
        }
        
        int possibleSquare = i * i;
        
        if(possibleSquare == numberToCheck)
        {
            return "Cool!";
        }
        
        if(possibleSquare > numberToCheck)
        {
            break;
        }
    }
    return "Not cool.."
}

Can't think of any more efficient solution other than doing a binary search on the range from [n; n/2]

so O(log n)

What's the optimal solution to this problem?

>>56173536
This is the solution on the site op got the challenge from:

class Solution {
public:
    bool isPerfectSquare(int num) {
        long long L = 1, R = (num >> 1) + 1;
        while (L <= R) {
            long long m = L + ((R - L) >> 1);
            long long mul = m * m;
            if (mul == num) return true;
            else if (mul > num) R = m - 1;
            else L = m + 1;
        }
        return false;
    }
};

>>56173200
With my haskell solution (>>56172019) ran in

time ./nrSqrt 18446744073709551615
True
./nrSqrt 18446744073709551615  0.00s user 0.00s system 64% cpu 0.007 total

on my Apple MacBook Pro™ (2011)

>>56173536
>[n; n/2]
[0; n/2] ofc

>>56165296

rt = sqrt(x);
if(rt - floor(rt) > 0)
    return false;
else
    return true;

1 Minute.
Literally kill yourself OP, you're retarded.

>>56173548
Well, this is just binary search from 1 to n/2 as well.
>tfw faggots use bitshifts to divide/multiply by 2^x although the compiler optimizes that shit anyway

File: 1384230623555.gif (726KB, 446x251px) Image search: [Google]

726KB, 446x251px

>>56173548
Imagine debug some legacy code an seeing that that shit on a friday at 14 pm.

>>56173576
>sqrt(x)
>Note: Do not use any built-in library function such as sqrt.

>>56173597
>14 pm

>>56173576
Also, not

return (rt - floor(rt) > 0)

Come on man.

>>56173599
And why the fuck not? Do I really have to implement one of the many well defined algorithms to fucking do it when every math library out there has this function?
Fuck off and kill yourself.

>>56165296
>do not use built-in library functions
maybe tell me to not use ASCII characters as well
fuck this worthless trivia shit

>>56173606
>not being in the orbit and having 48 hour days

>>56173576
>reading comprehension

File: 1377450511039.jpg (30KB, 396x385px) Image search: [Google]

30KB, 396x385px

>>56173548
Oh how I hate smart people

>>56173612
>>implement x
>why the fuck can't i use x what the fuck you fucking idiot op fuck you

Nobody else is as retarded as you anon

>>56173633
FUCK OFF
I HAVE A DEGREE IN COMPUTER SCIENCE AND THE ANSWER IS KILL URSELF

>>56173633
op didn't ask to implement a square root function

File: 1377591208184.jpg (8KB, 250x250px)

8KB, 250x250px

>>56173625
>that one guy that parses XML with binary operation.
>he handed in his 2 weeks notice
>you will take over his code
>no testing faze in your companys dev cycle ever

>>56173652
>>56173625
>Implying that's smart
Smart is writing readable, well documented code.

>>56173548
So I was right? Binary search on 0 to n/2 is the optimal solution?

aw yeah

>>56173678
I think he means people that just "see the solution".
You know the kind of guys that look at (their OWN) code and instantly know what each thing does.
The result is, just like you complain about, not well documented code.
>>56173691
Yup.

I'm different from all those other girls

and that's why I write my / 2 as >> 1

>>56172019
Best method desu senpai

>>56165296
Read about the modulo operator.

>>56173749
Damn, u smart gurl!

>>56173762
way more expensive than integer multiplication
why would you use it here?

>>56165296
Nah, that's too hard for /g/. Let's try something easier! Write a function returning (Nth Fibonacci number) modulo 1000000, N from 1 to 10^18.

>>56173784
So? I have money to pay for it.

>>56173855
that's literally homework

>>56173855

def fib(n):
    current = 1
    a = 1
    b = 1
    while True:
        current += 1
        a, b = b, a+b
        if current >= n:
            return a % 1000000

Untested. Written straight into the 4chan IDE box on your right.

>>56174528
will be too slow

it's a common exercise that wants you to use the matrix squaring method

>>56174662
>matrix squaring method
Not sure what that refers to, but I'm pretty sure the canonical solution to >>56173855 is to exploit the fact that modular fibonacci cycles very quickly

(It was one of the exercises in our cryptography introduction)

>>56174831
I had it as homework in my algorithm course.
Matrix squaring was expected there (fibonacci Q-matrix coupled with exponentiation by squaring).

Modulo was just there to avoid working with big ints

How to quickly shatter people's illusions about the speed of their computers:

for(int i=0;i<100000000;i++);

Write smarter algorithms.

>>56174893
matrix squaring can be improved to the fast doubling algorithm.

>>56173903
>fucking poorfags

>>56174940
That's pretty much the same, just the superfluous matrix stuff removed.
Both are O(log(n)) so it really doesn't matter for the exercise.

>>56175015
Fair enough, though it's still quicker.

>>56165296
i didnt enroll in CS to learn how to reimpliment math problems already solved in standard libraries

>>56175108
Then you should've picked an engineering curriculum, not a science one.

>>56174893
Do you still have the code? I would love to see how it compares to a naive modular solution.

[15:27][nand@nanodesu][/mem][130]
λ cat modfib.c
#include <stdio.h>

#define MODULO 1000000
unsigned int fibs[MODULO*10];

int main()
{
    // fill in the LUT
    fibs[0] = 0;
    fibs[1] = 1;
    unsigned int n = 0;
    do {
        fibs[n+2] = (fibs[n+1] + fibs[n]) % MODULO;
        n++;
    } while (fibs[n] != 0 || fibs[n+1] != 1);

    unsigned long x;
    while (scanf("%lu\n", &x) == 1)
        printf("%u\n", fibs[x % n]);
}
[15:27][nand@nanodesu][/mem]
λ gcc -O3 modfib.c -o modfib
[15:27][nand@nanodesu][/mem]
λ echo '1000000000000000000' | time ./modfib
546875
./modfib  0.01s user 0.00s system 89% cpu 0.010 total

>>56165296
>can you do this basic problem with basic solution?
>btw you can't do basic solution

File: 1471120098001.jpg (10KB, 220x255px) Image search: [Google]

10KB, 220x255px

>>56165296

using System;

namespace perfect_square
{
    class Program
    {
        public static bool findRoot(int arg)
        {
      
                for (int x = 1; ; x+=2)
                {
                    arg -= x;
                    if(arg <= 0)
                    {
                        if (arg == 0)
                            return true;
                        else
                            return false;
                    }
                }
        }
        static void Main(string[] args)
        {
            int usrNum;
            string res;
            Console.Write("Enter a positive number: ");
            usrNum = Convert.ToInt32(Console.ReadLine());
            if (findRoot(usrNum) == true)
            {
                res = "yes";
            }
            else
            {
                res = "no";
            }
            Console.WriteLine(res);
        }
    }
}

#include <stdio.h>

float Q_rsqrt(float number){
    long i;
    float x2, y;
    const float threehalves = 1.5f;

    x2 = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;
    i  = 0x5f3759df - ( i >> 1 );
    y  = * ( float * ) &i;
    y  = y * ( threehalves - ( x2 * y * y ) );
    y  = y * ( threehalves - ( x2 * y * y ) );

    return y;
}

bool check(int number){
    int root=1.0/Q_rsqrt(number)+0.5;
    
    return root*root == number;
}

int main(int argc,char **argv){
    printf("%d\n",check(715716)); // outputs 1; 715716=846^2
    printf("%d\n",check(715715)); // outputs 0
    
    return 0;
}

<?php
echo "
<form name=\"text\" method=\"post\" action=\"square.php\">
    <input name=\"text1\" type=\"text\" size=\"25\"></input>
    <input type=\"submit\" value=\"send\"></input>
</form>
";

if(isset($_POST['text1']) && is_numeric($_POST['text1'])){
    $n = $_POST['text1'];
    $res = cos(asin(((($n+1)/2)-1)/(($n+1)/2)))*(($n+1)/2);
    if(strpos($res,".")){
        echo "False";
    }else{
        echo "True";
    }
  }
?>

>>56173597
>14pm
But yeah finding code written without comments and retarded var names pisses me off. But then I've only worked at places where your code is reviewed by other people and the coding standards demand a certain quality of the code written. It's important when you have to blame someone for 900 people dying due to possible software error.

>>56173701
>Yup.
So how is that not brute forcing? Just because you reduced the problem size doesn't mean you eliminated the brute forcing part. This just shows that the people interviewing other people copy paste some interview question from the internet without understanding it themselves.

>>56174926
The compiler will optimize that to nop.

File: 1447436696947.png (199KB, 300x312px) Image search: [Google]

199KB, 300x312px

>>56175694

>>56172892
Here's my take on a binsearch solution

use std::env;

fn is_square(n: u64) -> bool {
    if n == 1 {
        true
    } else if n == 2 {
        false
    } else {
        let mut lo = 0;
        let mut hi = n/2;
        let mut result = false;

        while lo < hi {
            let mid = (lo + hi) / 2;
            let mid_sq = mid * mid;
            if mid_sq == n {
                result = true;
                break;
            } else if mid_sq < n {
                lo = mid + 1; //raise bounds
            } else {
                hi = mid - 1; //lower bounds
            }
        }
        result || hi * hi == n
    }
}

#[cfg(test)]
mod test {
    use super::is_square;

    #[test]
    fn positive() {
        let mut i = 1;
        while i < 10000 {
            assert!(is_square(i*i));
            i += 1;
        }
    }

    #[test]
    fn negative() {
        let mut i = 1;
        let mut psi = 1;
        let mut ps = 1; //next perfect square
        while i < 10000 {
            if i > ps {
                psi += 2;
                ps += psi;
            }
            if ps != i {
                assert!(!is_square(i));
            }
            i += 1;
        }
    }
}

fn main() {
    println!("{}",
             is_square(env::args()
                       .nth(1)
                       .expect("Argument required")
                       .parse()
                       .expect("Invalid arg")));
}

>>56175941
It doesn't work with 1000000000000000000 though, because the average overflows.
Gotta use

fn avg(x: u64, y: u64) -> u64 {
    x/2 + y/2 + (x%2 & y%2)
}

to average 2 numbers

Just use binary search bruh. 80% of problems have a good enough solution with some variant of binary search.

>>56176007
Here's a version that seems to work correctly with 9223372037000250000

use std::env;

fn avg(x: u64, y: u64) -> u64 {
    x/2 + y/2 + (x%2 & y%2)
}

fn is_square(n: u64) -> bool {
    if n == 1 {
        true
    } else if n == 2 {
        false
    } else {
        let mut lo = 0;
        let mut hi = n/2;
        let mut result = false;

        while lo < hi {
            let mid = avg(lo, hi);
            let mid_sq = if mid > 3037000499 {
                n+1 //lower bounds
            } else {
                mid * mid
            };
            if mid_sq == n {
                result = true;
                break;
            } else if mid_sq < n {
                lo = mid + 1; //raise bounds
            } else {
                hi = mid - 1; //lower bounds
            }
        }
        result || hi * hi == n
    }
}

#[cfg(test)]
mod test {
    use super::is_square;

    #[test]
    fn positive() {
        let mut i = 1;
        while i < 10000 {
            assert!(is_square(i*i));
            i += 1;
        }
    }

    #[test]
    fn negative() {
        let mut i = 1;
        let mut psi = 1;
        let mut ps = 1; //next perfect square
        while i < 10000 {
            if i > ps {
                psi += 2;
                ps += psi;
            }
            if ps != i {
                assert!(!is_square(i));
            }
            i += 1;
        }
    }
}

fn main() {
    println!("{}",
             is_square(env::args()
                       .nth(1)
                       .expect("Argument required")
                       .parse()
                       .expect("Invalid arg")));
}

Here is my pathetic excuse of a code

#include <stdio.h>
#include <stdlib.h>

int digitalRoot(int input){
    int digitalRoot = (1+(input-1)%9);
    // Debug Digital Root
    //printf("Digital Root: %d \n\n", digitalRoot);
    return digitalRoot;
}

int lastDigit(int input){
    int lastDigit = input % 10;
    // Debug LastDigit
    //printf("Last Digit: %d \n\n ", lastDigit);
    return lastDigit;
}

int perfectsquare(int input){

    //test if lastDigit is illegal
    int ld = lastDigit(input);
    if(ld == 2 || ld == 3 || ld == 7 || ld == 8)
        return 0;
    else {
    //test if digitalRoot is illegal
        int dr = digitalRoot(input);
        if(dr == 2 || dr == 3 || dr == 7 || dr == 8)
            return 0;
        else
            return 1;
    }
    
}

int main(int argc, char* argv[]){

    int input = 0;

    printf("Enter a number: ");
    scanf("%d", &input);
    printf("\n");

    if(perfectsquare(input))
        printf("number %d is perfectly square\n", input);
    else
        printf("number %d isn't perfectly square\n", input);

    return 0;
}

>>56175906
is something wrong, sir?

>>56176212
$ echo 16 | ./a.out
Enter a number:
number 16 isn't perfectly square

>>56176320
Oh I know, my digital root tester is shit.

>>56165371
>homework
>in august

>>56176456
Not completely unbelievable. I'm a student right now and have been at my university for six weeks already.

>>56175485
>didn't leave the comments in

>>56177539
what the fuck?

My attempt:

bool perfectsquare(uint64_t n) {
    // binary search O(log(n))

    if (!n or n==1) return true;
    uint64_t p = 0; //previous
    uint64_t i = 2;
    while (true) {
        uint64_t x = i*i;
        if (x == n) return true;
        if (i-p == 1) return false;
        
        if (x > n){
            i = (p + i) / 2;
        }
        else{
            p = i;
            i *= 2;
        }
    }        
}

I think the odd number sum solution is more efficient than the binary search. Sure the search is O(log(n)) in the number of integer multiplications and comparisons, but multiplication is more expensive than addition, and not by a constant factor. It's Implementation specific, but you might even have to do O(n) additions simply to generate the search range. So I think O(sqrt(n)) additions is the best approach.

>>56178642
I tried both and binary is MUCH faster

>>56178642
binary search will always win out in the end as O(sqrt(n)) is larger than O(logn). At some point the cost of individual operations doesn't matter.

>>56165387
>using more than 4 spaces

vomit.webm

>>56165296
MODULUS
O
D
U
L
U
S

>>56178864
The asymptomatic time could be different if the cost of the operations themselves are not both constant time.

Just make sieve of erestothenes and take modulus and divide if mod is zero twice with each prime, if no. becomes 1 then it is perfect square, if one mod is zero and 2nd mod is non zero with the same prime the number is not perfect square.

>>56165296
Pls do mah homewerk

well so far no one has posted a non-brute-force solution

congrats, you're all pajeets

>>56178864
But if your addition operation happens to be O(n) in the number of bits of your input, and multiplication happens to be O(n^2), then the sum solution is still O(sqrt(n)) while the binary search is O(log(n^2)) = O(n)

>>56172573
No it isn't you fucking autist. Just because you feel the need to justify your disability by tacking your own arbitrary bullshit onto other people's problems doesn't make it the case. Get a job, a girlfriend, and a life. Or kill yourself.

>>56179113
Stop using words you don't understand you stupid nigger.

>>56175770
This guy is really going to get butthurt when he learns the best solution to finding the nth fibbinochi sequence number.

>>56179166
>O(log(n^2)) = O(n)

wut. It doesn't matter what the cost of operation is you will always, quickly, get to the point where the number of addition operations out weigh the comparatively fewer multiplication ones. And of course you can improve the running tome of binary search if you give it multiple threads as well

>>56178642
For 32 bit int, worst cases:
Addition:: 2^30 operations
Binary search: 16 operations

>>56179299
Nah, he will be butthurt when he learns about complexities of square root computing algorithms. And that they fit his "definition" of """brute force""".

>>56179166
When you have an upper limit of an operation, for this example addition, the time complexity goes to O(1). Many algorithms use this fact. Trie is one that comes to mind. Time complexity is the growth rate of an operation.

>>56179166
>O(log(n^2)) = O(n)
hello Pajeet.

>>56179299
>>56179506
OP wanted an elegant solution implying there is a neat mathematical solution that doesn't require a binary search tree.

>>56179363
>>56179519
>>56179557

Think about it this way: if you define multiplication in terms of addition, squaring a number is adding n to itself n times.

So in the binary search every time you square a number you are doing O(n) additions. Clearly this is worse than doing sqrt(n) total additions for the odd number sum.

>>56179886
sqrt(n) total exponentiations, not additions

>>56179886
>Pajeet doesn't know any efficient multiplication algorithms so he resorts to using addition instead

>>56179886
>squaring a number is adding n to itself n times
Too bad multiplication is done in log(n) using only addition and bit shifting.

>>56179931
nope never mind additions, that's right, but the point is the number of additions needed as n grows increases much faster than just doing search

>>56179931
No, I'm talking about additions.

If you sum up the sequence of odd numbers until the result is greater than or equal n, you will know if n is a perfect square of the sum is strictly equal. This takes exactly sqrt(n) additions.

>>56179886
>if you use a totally inefficient way of doing things, I am right!

>>56179994
>>56179999
>>56180025

I used the most naive definition of multiplication to keep it simple, but the point is, multiplication is asymptomaticly less efficient than addition no matter how you implement it.

>>56180216
>I used the most naive definition
*totally inefficient
log^2 is still faster than sqrt.

I don't want to work for a company that won't allow me to use math.sqrt

Huge red flag right there

>>56180390
Math.sqrt only works for fixed precision numbers you fucking retard.

>>56180390
>I don't want to work for a company that makes me actually solve problems

Sounds about right.

>>56179732
What tree?

>>56180240
but if multiplication of n is O(n^2) and you need to perform multiplication of at most sqrt(n) at most logn times, wouldn't that bring the total runtime to O(nlogn)?

>>56180461
No Pajeet.

>>56180429
A genetic defect makes some people associate binary search with binary trees.
>>56180461
>>56179999

>>56180471
why not?

>>56180476
proof?

>>56179999
>>56180240

Even the fastest known multiplication algorithms are not log(n) in the number of bits.

>>56180500
I'm not a pro on genetic defects, sorry.

>>56180518
no the other thing lol

>>56170739
Found it: http://www.japanesebeauties.net/javhd/rei-aoki/1

>>56180515
Except n isn't the number of bits you fucking faggot.

>>56180515
...number of bits of n is literally log2(n)

>>56180524
Peasant multiplication.

>hurr multiplication
https://en.wikipedia.org/wiki/Wallace_tree

Multiplication is O(n) where n is the number of bits. This is simplified on real computers since n has an upper limit is 32 or 64 or what have you, to constant time.

Binary search is on an array, in this case the number line, not a real physical array.

I can safely say that after working both in automotive, rolling stock and the defence industry that most of you in this thread will never encounter problems like OP or interview style questions at all if you work in these sectors. In fact you will probably not even work with a normal programming language. You will build lego with logical gates and/or draw sequence diagrams for state machines.

>>56180696
If you use number of bits odds addition is no longer sqrt(n).

>>56180721
Different ns

>>56180746
What?

>>56180746
Obviously. But people could be confused. Why did you choose that metric, even?

>>56180696
>Multiplication is O(n) where n is the number of bits.

no it isn't

>>56180787
In hardware, it has one propagation layer per bit, so it is. But it's retarded metric. >>56180551

>>56180831
what

>>56165296

function findmyshit(num){
  if((num**.5)%1 === 0) {
    return true
  }
  else { return false }
}

>>56180771
That's what shift and add is dependant on.

>>56180216
>multiplication is asymptomaticly less efficient than addition no matter how you implement it.
no, on current hardware multiplication is just as fast as addition, imul takes 1-2 cycles on Skylake for 64-bit operands. source: http://www.agner.org/optimize/instruction_tables.pdf

(defun check (a)(= a (do ((i 0 (1+ i)))((>= (* i i) a)(* i i)))))

easy. just 1 line

>>56181158
If we're just talking about fixed bit integers than the fastest way to do this is to use a lookup table.

>>56170669
This is the optimum solution for you

function arrayContains(arr, val) {
    for (var i=0; i<arr.length; i++) {
        if (arr[i] === val) {
            return true;
        }
    }
    return false;
}

var rejectedBy = [];
var mLady = false;

for (standardsLevel=100; ! mLady; standards--) {
    var daWimmin = getSingleWomenOnPlentyOfFish({
        milesFromMe: Math.round(15 + (100-standardsLevel)/2)
    });

    for (index in daWimmin) {
        var potentialBae = daWimmin[index];
        if (potentialBae.quality < standards || arrayContains(rejectedBy, potentialBae.id)) {
            continue;
        }

        potentialBae.sendMessage('hey gurl i have a stable job and a car and i think you\'re pretty sexy. lemme treat you right 2nite');

        if (potentialBae.isDisgusted()) {
            rejectedBy.push(potentialBae.id);
            continue;
        }

        potentialBae.askOut();

        if (potentialBae.accepted()) {
            mLady = potentialBae;
            break;
        } else {
            rejectedBy.push(potentialBae.id);
        }
    }
}

if (! mLady) {
    killSelf();
}

>>56180461
yeah I see what I did wrong here, I'm using n to represent 2 different things. So given that the bit complexity of multiplication is O(N^2) with N the number of bits, and the number of bits of some number M is log2(M), binary search has complexity

log2(M)^2

compared to sqrt(M) additions of bit complexity log(M) or

sqrt(M)log(sqrt(M))

???