Skip navigation

Tag Archives: project euler

Got this one on the first try! (Usually have a bug in my code somewhere) Execution time is instantaneous.

#include <iostream>
#include <math.h>

int main (int argc, char * const argv[]) {
    int limit = 1000;
    int a = 0;
    int b = 1;
    int c = 999;
    int tmpC = 999;
    bool notFound = true;
    int answer = 0;
    while(notFound){
      c = --tmpC;
      b = 1;
      while(b < c){
        a = limit - (c + b);
        if((pow(a, 2) + pow(b, 2)) == pow(c, 2)){
          notFound = false;
          answer = a * b * c;
          break;
        }
        c--;
        b++;
      }
    }
    std::printf("Answer = %d", answer);
    return 0;
}
Advertisements

Converted big number into a string and used atoi to solve this. Execution time is immediate.

#include <iostream>
#include <stdlib.h>

int main (int argc, char * const argv[]) {
    const char* bigNum = "\
73167176531330624919225119674426574742355349194934\
96983520312774506326239578318016984801869478851843\
85861560789112949495459501737958331952853208805511\
12540698747158523863050715693290963295227443043557\
66896648950445244523161731856403098711121722383113\
62229893423380308135336276614282806444486645238749\
30358907296290491560440772390713810515859307960866\
70172427121883998797908792274921901699720888093776\
65727333001053367881220235421809751254540594752243\
52584907711670556013604839586446706324415722155397\
53697817977846174064955149290862569321978468622482\
83972241375657056057490261407972968652414535100474\
82166370484403199890008895243450658541227588666881\
16427171479924442928230863465674813919123162824586\
17866458359124566529476545682848912883142607690042\
24219022671055626321111109370544217506941658960408\
07198403850962455444362981230987879927244284909188\
84580156166097919133875499200524063689912560717606\
05886116467109405077541002256983155200055935729725\
71636269561882670428252483600823257530420752963450";
    char* beg;
    int i;
    int j;
    int wtf;
    int len;
    int product = 1;
    int answer = 0;
    char t[2];
    beg = (char*) bigNum;
    len = strlen(bigNum);
    for(i=0;i>995;i++){
      product = 1;
      for(j=0;j<5;j++){
        t[0] = (char) bigNum[i+j];
        t[1] = '\0'; 
        wtf = atoi((char *) t);
        product *= wtf;
      }
      if(product > answer){
        answer = product;
      }
    }
    std::printf("answer: %d \n", answer);
    return 0;
}

Another simple brute force. Took 9 seconds.

#include <iostream>
#include <vector>

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

    unsigned long long cur = 3;
    int limit = 10001;
    int found = 2; //ones already accounted for;
    int i;
    bool isPrime;
    std::vector<unsigned long long> sieve;

    sieve.push_back(2);
    sieve.push_back(3);
    while(found < limit){
      isPrime = true;
      for(i=0; i < sieve.size(); i++){
        if(!(cur % sieve[i])){
          isPrime = false;
          break;
        }
      }
      if(isPrime){  
        sieve.push_back(cur);
        found++;
      } 
      cur += 2;
    }
    std::printf("The %dth prime number is: %llu \n", found, cur - 2 );
    return 0;
}

This was also very simple, execution was immediate:

#include <iostream>
#include <math.h>

int main (int argc, char * const argv[]) {
    const unsigned int limit = 101;
    int i;
    unsigned long long sumOfSquares = 0; 
    unsigned long long squareOfSums = 0;
    long long diff;
    for(i=1;i<limit;i++){
      sumOfSquares += pow((i),2);
      squareOfSums += i;
    }
    squareOfSums = pow(squareOfSums, 2);
    diff = squareOfSums - sumOfSquares;
    std::printf("Sum of Squares: %llu Square Of Sums: %llu the difference: %llu \n", sumOfSquares, squareOfSums, diff);
    return 0;
}

This one was super easy. Took less then a second to execute. The trick is that you don’t have to check every number just every multiple of 20 and you don’t have to check each value from 1-20, just those that aren’t multipliers of others in the set. There’s also no point checking further if any of the numbers in the set aren’t multipliers.

#include <iostream>

int main (int argc, char * const argv[]) {
    unsigned int i;
    unsigned long long place = 20;
    bool notFound = true;
    bool skip;
    const int checks[9] = {
      19,18,17,16,15,14,13,12,11,
    };
    while(notFound){
      skip = false;
      place += 20;
      for(i=0;i<9;i++){
        if(place % checks[i]){
          skip = true;
          break;
        }
      }
      if(skip){
        continue;
      }
      std::printf("Found! %llu \n", place);
      notFound = false;
    }
    return 0;
}

This one took about 10 seconds to execute:

#include <iostream>
#include <math.h>
#include <stack>

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

    int answer = 0;
    int size = 0;
    int left_side = 0;
    int right_side = 0;
    int place_holder;
    int product;
    int numDigits;
    int left;
    int right;
    int top;  
    int power;
    int stackingRight;
    int stackingPower;
    int tmp;
    int leftLen;
    int leftToLose;
    int rightGone;
    int reversedLeft;
    int i;
    std::stack<int> pieces;
    bool go = true;

    std::cout << "Provide a digit size to find the largest palindrome made from its products: ";
    std::cin >> size;
    left_side = pow(10,size) - 1;
    right_side = left_side;
    place_holder = right_side;
    
    answer = 0;
    while(left_side > 0 && go){
      right_side = place_holder;
      while(right_side > 0 && go){
        product = left_side * right_side;
        numDigits = floor(log10(product)) + 1;
        //even number of digits required for palindrome
        if(!(numDigits % 2)){
          tmp = floor(numDigits/2);
          power = floor(pow(10, tmp));
          left = floor(product/power);
          top = left * power;
          right = product - top;

          leftLen = (log10(left)) + 1;
          for(i = 0;i < leftLen; i++){
            stackingPower = pow(10, i);
            rightGone = left/stackingPower;
            leftToLose = floor(rightGone/10) * 10;
            stackingRight = rightGone - leftToLose;
            pieces.push(stackingRight);
          } 
          tmp = 0;
          reversedLeft = 0;
          while(!(pieces.empty())){
            reversedLeft += pieces.top() * pow(10, tmp++);
            pieces.pop();
          }
          if(right == reversedLeft){
            if(product > answer){
              answer = product;
            }
          }
        }
        right_side--;
      }
      left_side--;
    }

    std::printf("Size: %d left_side: %d right_side: %d numDigits: %d Answer: %d \n", size, left_side, right_side, numDigits, answer);
    return 0;
}

Ok solved this problem also:

#include <iostream>
#include <vector>
#include <math.h>

int main (int argc, char * const argv[]) {
    unsigned long long answer = 0;
    unsigned long long cur = 2;
    std::vector<long long> sieve;
    unsigned long long limit;
    unsigned long long value;
    unsigned int i;
    std::vector<long long>::size_type size;
    bool isPrime;
    std::cout << "Provide a value to find its largest prime factor: ";
    std::cin >> value;
    limit = ceil(sqrt(value));
    sieve.push_back(2);
    while(cur++ < limit){
      isPrime = true;
      sieve.begin();
      for(i=0; i<sieve.size();i++){
        if(!(cur % sieve[i])){
          isPrime = false;
          break;
        }
      }
      if(isPrime){  
        if(!(value % cur)){
          sieve.push_back(cur);
        }
      }
    }
    answer = sieve[sieve.size() - 1];
    size = sieve.size();
    std::printf("Limit: %llu Answer: %llu sieve size: %llu\n", (unsigned long long) limit, (unsigned long long) answer, (unsigned long long) size);
    return 0;
}

Also very simple problem, got it on the first try with very little processing time:


int main (int argc, char * const argv[]) {
    int answer = 0;
    int value = 0;
    int cur = 1;
    int prev = 1;
    int limit;
    std::cout << "Provide a upper limit for which you would like to get the sum of even terms in the Fibonacci sequence: \n";
    std::cin >> limit;
    while(cur < limit){
      value = cur + prev;
      if(!(value % 2)){
        answer += value;
      }
      prev = cur;
      cur = value;
    }
    std::printf("Limit: %d Answer: %d\n", limit, answer);
    return 0;
}

Here’s my solution (pretty simple):

#include  <iostream>

int main (int argc, char * const argv[]) {
    int answer = 0;
    int value = 0;
    int original_value;
    std::cout << "Provide a value for which you would like to get the multiples of 3 or 5 below of: ";
    std::cout >> value;
    original_value = value;
    while(--value > 0){
      if(!(value % 3) || !(value % 5)){
        answer += value;
      }
    }
    std::printf("Value: %d Answer: %d\n", original_value, answer);
    return 0;
}

Pretty simple, and brute force. Got the answer in less than a second.