code

UVA Problem 438 – The Circumference of the Circle Solution

Posted on December 18, 2015 by quickgrid

UVA Problem 438 – The Circumference of the Circle Solution:

Click here to go to this problem in uva Online Judge.

Solving Technique:

Given three points find the circumference of the circle. Points are non-collinear meaning they are not on a straight line.

Have a look at Circumscribed circle, Semi perimeter and Heron’s formula to find more about the formula and derivation.

Also related to this have a look at UVA 10432 – Polygon Inside a Circle.

Important: Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are in c and some in c++.

More Inputs of This Problem on uDebug.

Input:

0.0 -0.5 0.5 0.0 0.0 0.5
0.0 0.0 0.0 1.0 1.0 1.0
5.0 5.0 5.0 7.0 4.0 6.0
0.0 0.0 -1.0 7.0 7.0 7.0
50.0 50.0 50.0 70.0 40.0 60.0
0.0 0.0 10.0 0.0 20.0 1.0
0.0 -500000.0 500000.0 0.0 0.0 500000.0

Output:

Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 438 - The Circumference of the Circle.
 * Technique: Finding diameter and circumference of Circumscribed
 *            circle or Circumcircle.
 *            Using Heron's formula to calculate semi perimeter
 *            and area of triangle from Three points.
 */

#include<stdio.h>
#include<string.h>
#include<math.h>


#define PI 3.141592653589793


int main(){

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);


    double x1, y1;
    double x2, y2;
    double x3, y3;


    while( scanf("%lf%lf%lf%lf%lf%lf", &x1, &y1, &x2, &y2, &x3, &y3 ) == 6 ){

        // a dist between (x1,y1) and (x2,y2)
        // b dist between (x2,y2) and (x3,y3)
        // c dist between (x3,y3) and (x1,y1)

        double a = sqrt( pow(x1 - x2, 2) + pow(y1 - y2, 2) );
        double b = sqrt( pow(x2 - x3, 2) + pow(y2 - y3, 2) );
        double c = sqrt( pow(x3 - x1, 2) + pow(y3 - y1, 2) );


        // semi perimeter, s = (a+b+c)/2

        double s = ( a + b + c ) / 2;


        // Area using Heron's Formula

        double A = sqrt( s*(s-a)*(s-b)*(s-c) );


        // Diameter of circumscribed circle d = abc/2A

        double d = (a * b * c) / (2 * A);


        // Result circumference of the circumcircle or circumscribed circle

        double circumference = PI * d;


        printf("%.2lf\n", circumference );

    }


    return 0;
}

Unnecessary Complex Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 438 - The Circumference of the Circle.
 * Technique: Point and Line representation in structure.
 *            Finding diameter and circumference of Circumscribed
 *            circle or Circumcircle.
 *            Using Heron's formula to calculate semi perimeter
 *            and area of triangle from Three points.
 */

#include<stdio.h>
#include<string.h>
#include<math.h>


#define PI 3.141592653589793


struct Point{
    double x;
    double y;
};


struct Line{
    Point a;
    Point b;

    Point setPoints( Point _a = {0.0,0.0}, Point _b = {0.0,0.0} ){
        a = _a;
        b = _b;
    }

    double length(){
        return sqrt( pow(a.x - b.x, 2) + pow(a.y - b.y, 2) );
    }

};


int main(){

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);


    Point point[3];
    Line  line [3];


    while( scanf("%lf%lf%lf%lf%lf%lf", &point[0].x, &point[0].y, &point[1].x, &point[1].y, &point[2].x, &point[2].y ) == 6 ){


        // Loop is same as code below.
        //line[0].setPoints(point[0], point[1]);
        //line[1].setPoints(point[1], point[2]);
        //line[2].setPoints(point[2], point[0]);

        int N = 3;
        for( int i = 0; i < N; ++i )
            line[i].setPoints( point[i], point[(i+1) % N] );



        // semi perimeter is half of perimeter.
        // Perimeter is distance around the shape in 2D.

        double s = ( line[0].length() + line[1].length() + line[2].length() ) / 2;


        // Area using Heron's Formula

        double A = sqrt( s * (s - line[0].length()) * (s - line[1].length()) * (s - line[2].length()) );


        // Diameter of circumscribed circle d = abc/2A

        double d = (line[0].length() * line[1].length() * line[2].length()) / (2 * A);


        // Result circumference of the circumcircle

        double circumference = PI * d;


        printf("%.2lf\n", circumference );

    }


    return 0;
}

UVA Problem 10432 – Polygon Inside A Circle Solution

Posted on December 12, 2015 by quickgrid

UVA Problem 10432 – Polygon Inside A Circle Solution:

Click here to go to this problem in uva Online Judge.

Solving Technique:

This is a rather easy geometry / computational geometry problem. Given the radius of a Circumscribed circle and count of sides of a polygon the task is to find the area of the polygon. A Circumscribed circle is a circle that passes through all vertices of a plane figure and contains the entire figure in its interior.

The formula below can be written into a single formula by combining all the formulas. More information and the combined formula can be found here.

Learn more about regular polygon here including the formula.

Visual Explanation:

I have tried to explain the concept below using figures. They are not drawn to scale. The small circles represent intersection point between polygon vertices and the circumscribed circle.

Example:

It is an example with radius, r = 2 and sides, n = 8.

More Inputs of This Problem on uDebug.

Input:

2 2000
10 3000

Output:

12.566
314.159

Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 10432 - Polygon Inside A Circle
 * Technique: circumcircle Or, Isocele Area calculation.
 */

#include<stdio.h>
#include<string.h>
#include<math.h>


int main(){

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);


    double r;
    int n;

    while( scanf( "%lf%d", &r, &n ) == 2 ){

        // Angle between each two points for every point.
        double PHI = ( double ) 360 / n ;

        // For each Isosceles in the polygon the angle between the base and radius.
        double THETA = (double) 90 - ( PHI / 2 );


        // Convert Degree angle to Radian to use in code.
        double THETA_RADIAN = THETA * M_PI / 180;


        //  a is base.
        double a = 2 * r * cos( THETA_RADIAN );

        // H is the height.
        double h = r * sin( THETA_RADIAN );

        // S represent Area of a single segment.
        double S = (a * h) / 2;


        // S * n is the are of complete polygon.
        printf("%.3lf\n",  S * n );


    }

    return 0;
}

UVA Problem 417 – Word Index Solution

Posted on December 12, 2015December 12, 2015 by quickgrid

UVA Problem 417 – Word Index Solution:

Click here to go to this problem in uva Online Judge.

Solving Technique:

This one of the worst code I have ever written. It is both slow and wastes huge amount of memory, but still works. I am sharing this code as an example 5 dimensional re-sizable (vector) array. There are far far far better solution than this, so I won’t explain it.

If the input is thought of as string, then for each position the character right to current character is at least current character plus one. Since there are 5 length classes 1,2,3,4,5. So for each of them I applied this logic.

More Inputs of This Problem on uDebug.

Input:

Output:

z
a
cat
vwxyz

Code:

/**
 * Author:    Asif Ahmed
 * site:      quickgrid.wordpress.com
 * Problem:   UVA 417 - word index
 * Technique: Very Slow and worst possible solution.
 *            5 (five) dimensioanl vector integer array. 1, 2
 *            3, 4 (four) dimensional integer array.
 */

#include <vector>
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;


#define N 26


int main() {


    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);


    vector<vector<vector<vector<vector<int> > > > > array5d;


      array5d.resize(N);
      for (int i = 0; i < N; ++i) {
        array5d[i].resize(N);

        for (int j = 0; j < N; ++j){
          array5d[i][j].resize(N);

            for (int k = 0; k < N; ++k){
              array5d[i][j][k].resize(N);

                for (int m = 0; m < N; ++m){
                  array5d[i][j][k][m].resize(N);
                }

            }
        }

      }

        int s1[N];
        int s2[N][N];
        int s3[N][N][N];
        int s4[N][N][N][N];
        int n = 0;


        for(int i = 0; i < N; ++i)
            s1[i] = ++n;



        for(int i = 0; i < N; ++i){
            for(int j = i + 1; j < N; ++j){
                s2[i][j] = ++n;

            }
        }



        for(int i = 0; i < N; ++i){
            for(int j = i + 1; j < N; ++j){
                for(int k = j + 1; k < N; ++k){

                        s3[i][j][k] = ++n;

                }
            }
        }




        for(int i = 0; i < N; ++i){
            for(int j = i + 1; j < N; ++j){
                for(int k = j + 1; k < N; ++k){
                    for(int m = k + 1; m < N; ++m){

                        s4[i][j][k][m] = ++n;

                    }
                }
            }
        }




        for(int i = 0; i < N; ++i){
            for(int j = i + 1; j < N; ++j){
                for(int k = j + 1; k < N; ++k){
                    for(int m = k + 1; m < N; ++m){
                        for(int t = m + 1; t < N; ++t){

                            array5d[i][j][k][m][t] = ++n;

                        }

                    }
                }
            }
        }




        char input[N];

        while( gets(input) ){

            int len = strlen(input);

            switch(len){
            case 1:
                printf("%d\n", s1[ input[0] - 'a' ] );
                break;
            case 2:
                printf("%d\n", s2[ input[0] - 'a' ][ input[1] - 'a' ] );
                break;
            case 3:
                printf("%d\n", s3[ input[0] - 'a' ][ input[1] - 'a' ][ input[2] - 'a' ] );
                break;
            case 4:
                printf("%d\n", s4[ input[0] - 'a' ][ input[1] - 'a' ][ input[2] - 'a' ][ input[3] - 'a' ] );
                break;
            case 5:
                printf("%d\n", array5d[ input[0] - 'a' ][ input[1] - 'a' ][ input[2] - 'a' ][ input[3] - 'a' ][ input[4] - 'a' ] );
                break;
            }

       }



  return 0;
}

UVA Problem 11716 – Digital Fortress Solution

Posted on December 10, 2015 by quickgrid

UVA Problem 11716 – Digital Fortress Solution:

Click here to go to this problem in uva Online Judge.

Solving Technique:

This is an easier string problem. The task is to arrange the characters within the string in a certain order.

If the input string length is not square of a number then print INVALID. Ex: “DAVINCICODE” has length of 11. Squaring no number results in 11.

“DTFRIAOEGLRSI TS” has length of 16 including the space character. Square root of 16 is 4 and 4 * 4 is 16. So this is valid input.

Now if the input is valid then next task is to rearrange them. Instead of following given solution technique in the question it can solved much faster in another way. Following instruction in the question gives intuition that first the string must be positioned on 2 dimensional matrix in row major order. Then traverse them column by column.

A better way is find out each group length from square rooting the original string length. Next starting from first group take a character then skip by group length to get next column major character. After its done do this from the next character of first group.

Visualization:

uva 11716 rearrange string in column major order

More Inputs of This Problem on uDebug.

Input:

3
WECGEWHYAAIORTNU
DAVINCICODE
DTFRIAOEGLRSI TS

Output:

WEAREWATCHINGYOU
INVALID
DIGITAL FORTRESS

Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 11716 - Digital Fortress
 * Technique: Square String Traverse from row major
 *            to column major by skipping.
 */

#include<stdio.h>
#include<string.h>
#include<math.h>


#define N 10002
static char s[N];
static char output[N];


int main(){

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);


    int n;
    scanf("%d", &n);
    getchar();


    while( n-- ){
        gets(s);


        // Get the length of string and length of each string group.
        int len = strlen(s);
        int rc = sqrt(len);


        // Reset in case there are characters from previous iteration.
        memset(output, 0, sizeof output);



        // If the string length can be divided into equal parts
        // then traverse by skipping certain length.
        if( rc * rc == len ){

            int k = 0;

            for( int j = 0; j < rc; ++j ){
                for( int i = j; i < len; i = i + rc ){
                    output[k++] = s[i];
                }
            }

            puts(output);

        }
        else{
            puts("INVALID");
        }

    }


    return 0;
}

Fibonacci Number Generation with Golden Ratio Code

Posted on November 20, 2015 by quickgrid

The formula and explanation are all available in here in wikipedia. It won’t produce correct result for any number greater than 70.

Code Fibonacci Generation with Golden ratio:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   Fibonacci number generation using golden ratio.
 * Technique:
 */

#include<bits/stdc++.h>
using namespace std;


int main(){

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    long double phi  = 1.61803398874989484820458683436563811772030917980576286213544862270526046281890;
    long double phiN = 0.61803398874989484820458683436563811772030917980576286213544862270526046281890;


    // Change value of n to desired value.
    // Should give correct Fibonacci value for 1 to 70.
    int n = 70;

    long double F = ( pow(phi, n) - pow( phiN, n ) ) / sqrt(5);

    cout.setf(ios::fixed);
    cout << setprecision(0) << round(F) << "\n";



    return 0;
}

UVA Problem 913 – Joana and the Odd Numbers Solution

Posted on November 17, 2015November 21, 2015 by quickgrid

UVA Problem 913 – Joana and the Odd Numbers Solution:

Click here to go to this problem in uva Online Judge.

Solving Technique:

Todo:
1. Reorganize.
2. check for mistakes.

This problem can be solved in quite a few ways. Brute force won’t work. I have given the brute force code anyway. It will give correct answer from 1 < n < 199999999 but the requirement is 1 < N < 1000000000, which is way way larger.

Another approach is to do mathematical calculation to come up with a formula to solve this. Multiple formula can be generated such as a single formula or, one formula complementing other or, multiple formula's combined. I have provided two formula in the codes below.

One thing to mention, the output or input must be long long data type. Other data types will give incorrect output.

Unfortunately I won’t be elaborate more than this. It took 5 pages to solve this many way with proof, but that’s a lot to write. I will try to explain a way for coming up with these formula.

The brute force way:

A simple way to do this is, for values greater than 1 set offset 10 and start multiplying with 5. For each step increase offset by 4 and add value to previous multiplying value.

Input -> Sum

3 -> 3 * 5
5 -> 3 * 15, [ 15 = 5 + 10 ]
7 -> 3 * 29, [ 29 = 15 + 14 ]
9 -> 3 * 47, [ 47 = 29 + 18 ]
11 -> 3 * 69, [ 69 = 47 + 22 ]
13 -> 3 * 95, [ 95 = 69 + 26 ]

Although this approach will not work since the range is huge. It is possible to pre-calculate for a certain range and anything outside that calculate with formula.

Trying to Come up with a Closed Form Expression:

First thing is to notice is that the numbers differ by 2 and are odd. So, if the first number is n, then the sum of n and next two numbers is,

$n + ( n + 2 ) + ((n + 2) + 2) = n + n + 2 + n + 4 = 3n + 6$

Ex:
If n was 67, then result of 3n + 6 = 207.

The opposite is also true. For example, given sum of three numbers we can find the first number by,
if sum was 141 then,

$3n + 6 = 141 => n = 45$

Expanding and writing the sequence in format below,

Input – Values in the Row(Last three numbers bracketed) – Sum

1 - [ 1 ] - 1
3 - [ 3 5 7 ] - 15 
5 - 9 11 [ 13 15 17 ] - 45
7 - 19 21 23 25 [ 27 29 31 ] - 87  
9 - 33 35 37 39 41 43 [ 45 47 49 ] - 141
11 - 51 53 55 57 59 61 63 65 [ 67 69 71 ] - 207
13 - 73 75 77 79 81 83 85 87 89 91 [ 93 95 97 ] - 285

This means for a given value there are that many numbers in that row.

Trying to come up with a Brute Force Approach:

This is extra and not required to solve this problem but it will understand creation of the formula.

The first numbers of every row can be generated and memoized in a table sequentially using the formula below,
row – number break down – first number

1 -> 1 -> 1
3 -> 1 + ( 1 * 2 ) -> 3
5 -> 3 + ( 3 * 2 ) -> 9
7 -> 9 + ( 5 * 2 ) -> 19
9 -> 19 + ( 7 * 2 ) -> 33

Let n1 be equal to 1 and n2, n3 …, nk be next generated sequences. So the formula is,
n1 = n1
n2 = n1 + (1 * 2)
n3 = n2 + (3 * 2)
n4 = n3 + (5 * 2)
n5 = n4 + (7 * 2)
……………..
……………..
nk = n(k-1) + (i * 2)

this can be converted to an algorithm,
Let, T be table to store value of the first number.
n1 = 1
T[n1] = n1

i = 3

for i to size
T[i] = T[i-2] + (i-2) * 2
increment i by two
End

Generating Solution From the Output:

sum sequence calculation in terms of value

Similarly, The sum can also be calculated in terms of input by creating a sequence and finding out the formula.

1 -> 1
3 -> 15
5 -> 45
7 -> 87
9 -> 141
11 -> 207
13 -> 285

when they are written in a sequence,

1 + 15 + 45 + 87 + 141 + 207 + 285 + …………..

So, for 11 the output should be 207. The formula can be calculated from the picture above

207 = 141 + 66
207 = 141 + (54 + 12)
207 = 141 + ((12 * 5) – 6 + 12)
207 = 141 + ((12 * 6) – 6)
207 = 87 + 54 + ((12 * 6) – 6)
207 = 87 + ((12 * 5) – 6) + ((12 * 6) – 6)
207 = 45 + ((12 * 4) – 6) + ((12 * 5) – 6) + ((12 * 6) – 6)
207 = 15 + ((12 * 3) – 6) + ((12 * 4) – 6) + ((12 * 5) – 6) + ((12 * 6) – 6)
207 = 1 + ((12 * 2 – 6) – 4) + ((12 * 3) – 6) + ((12 * 4) – 6) + ((12 * 5) – 6) + ((12 * 6) – 6)
207 = (12 * 2 – 6) + ((12 * 3) – 6) + ((12 * 4) – 6) + ((12 * 5) – 6) + ((12 * 6) – 6) – 3

this can be written as summation formula,

$-3 + \sum_{i = 2}^{ceil( \frac{n}{2} )} 12i - 6$

this can be rewritten as,
$-3 + 6 * \sum_{i = 2}^{ceil( \frac{n}{2} )} 2i - 1$

The input for this formula is the input for the program,
for, n = 17 the sum of last three numbers should be 477.
Setting n = 17 in following the formula it will give,

-3 + 6 * ( 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17 ) = 477

The formula above doesn’t quite work out for 1. Although we know for 1 output is 1 but it should be included in the formula. Expanding and changing values the summation will get the formula for all values.

Similarly, this is the formula to calculate the first number to sum from a row. It was calculated making a sequence of first summing numbers and find out the the summation formula,

First number,
$N = 3 + 2 * \sum_{i = 2}^{floor( \frac{n}{2} )} 2i + 1$

Separating the summation,
$\sum_{i = 2}^{floor( \frac{n}{2} )} 2i + 1 = 2 * \sum_{i = 2}^{floor( \frac{n}{2} )} i + \sum_{i = 2}^{floor( \frac{n}{2} )} 1$

$= 2 * ( \sum_{i = 1}^{floor( \frac{n}{2} )} i - \sum_{i = 1}^{ 1 } i ) + \sum_{i = 1}^{floor( \frac{n}{2} )} 1 - \sum_{i = 1}^{ 1 } 1$

$= 2 * \sum_{i = 1}^{floor( \frac{n}{2} )} i - 2 + \sum_{i = 1}^{floor( \frac{n}{2} )} 1 - 1$

$= floor( \frac{n}{2} ) ( floor( \frac{n}{2} ) + 1 ) + floor( \frac{n}{2} ) - 3$

I won’t simplify anymore.

Put the value of summation in the equation,
$N = 3 + 2 * \sum_{i = 2}^{floor( \frac{n}{2} )} 2i + 1$
because i only expanded the summation. Multiply result with 2 and add 3 to get the first number.

From, the equation above place the value of first number in 3n + 6 to get the summation of last three numbers for a given number.

The 3n + 6 and the summation formula can be combined into a single formula.

Generating Solution based on First Number of Last Three:

Similarly the first number to sum from every row can be calculated. If the first number from every row are written in a sequence,

1 + 3 + 13 + 27 + 45 + 67 + ………………..

The first number can be generated following this,

summation first number generation for an input

For input n = 11, task is to generate first number from the graphical representation above. Then the value can be placed in equation, 3N + 6 to generate sum of that value and next two (basically the answer).

67 = 45 + 22
67 = 45 + ( 18 + 4 )
67 = 45 + ( 14 + 4 + 4 )
67 = 45 + ( 10 + 4 + 4 + 4 )
67 = 45 + ( 10 + 4 + 4 + 4 )
67 = 27 + 18 + ( 10 + 4 + 4 + 4 )
67 = 27 + ( 10 + 4 + 4 ) + ( 10 + 4 + 4 + 4 )
67 = 13 + 14 + ( 10 + 4 + 4 ) + ( 10 + 4 + 4 + 4 )
67 = 13 + ( 10 + 4 ) + ( 10 + 4 + 4 ) + ( 10 + 4 + 4 + 4 )
67 = 3 + 10 + ( 10 + 4 ) + ( 10 + 4 + 4 ) + ( 10 + 4 + 4 + 4 )
67 = 3 + 10 + ( 10 + 4 ) + ( 10 + 4 + 4 ) + ( 10 + 4 + 4 + 4 )

this way the formula can be,

$First \ number = 3 + \sum_{i = 1}^{ floor( \frac{n}{2} - 1 ) } 10 + \sum_{i = 1}^{ floor( \frac{n}{2} - 2 ) } 4i$

$First \ number = 3 + 10 * \sum_{i = 1}^{ floor( \frac{n}{2} - 1 ) } 1 + 4 * \sum_{i = 1}^{ floor( \frac{n}{2} - 2 ) } i$

$First \ number = 3 + 10 * ( floor( \frac{n}{2} ) - 1 ) + 2 * ( floor( \frac{n}{2} ) - 2 ) * ( floor( \frac{n}{2} ) - 1 )$

This can be further simplified.

For n = 15 the first number should be 123. Setting n = 15 in equation above,

first number = 3 + 10 * ( 7 – 1 ) + 2 * ( 7 – 2 ) * ( 7 – 1 )
first number = 3 + 60 + 60 = 123

That’s it. There are other approaches but it will take a long time to write.

More Inputs of This Problem on uDebug.

Input:

3
5
7

Output:

15
45
87

Formula Generate sequence sum, first number & sum Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 913 Joana and Odd numbers
 * Technique: Generate Sequence Sum, First number
 *            then generate sum of next numbers
 *            including the generated number.
 */

#include<stdio.h>
#include<string.h>


int main(){

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);


    long long n;

    while( scanf("%lld", &n) == 1 ){

        long long m = n >> 1;

        long long part = ( (n * (n + 1)) >> 1 ) - ( m * ( m + 1 ) ) - 4;

        long long firstNum = 2 * part + 3;

        printf("%lld\n", 3 * firstNum + 6);

    }


    return 0;
}

Reduced Formula Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 913 Joana and Odd numbers
 * Technique: Reduced formula.
 */

#include<stdio.h>
#include<string.h>


int main(){

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    unsigned long long n;

    while( scanf("%lld", &n) == 1 ){

        long long ans =  3 * ( (n + 1) * ( n - (n >> 1) ) )  - 9;

        printf("%lld\n", ans);
    }


    return 0;
}

Brute Force Code( Won’t be Accepted ):


/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 913 - Joana and the odd numbers
 * Technique: Brute Force. Won't get Accepted.
 *            This is just for demonstration. This
 *            won't get accepted due to huge size that
 *            array can't process. But it will give correct
 *            answer till N.
 */

#include<stdio.h>
#include<string.h>


#define N 100000000
//#define M 1000000000


static long long value[N];


int main(){

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);


    value[0] = 1;
    value[1] = 15;
    long long offset = 30;


    for( long long i = 2; i < N; ++i ){
        value[i] = value[i-1] + offset;
        offset = offset + 12;
    }


    long long n;
    while( scanf("%lld", &n) == 1 ){
        printf("%lld\n", value[n/2] );
    }


    return 0;
}

UVA Problem 10106 – Product Solution (Lattice Multiplication)

Posted on November 16, 2015November 16, 2015 by quickgrid

UVA Problem 10106 – Product Solution:

Click here to go to this problem in uva Online Judge.

Solving Technique:

This problem is quite simple. Given two very large integers multiply them and print them. By large I mean almost 251 characters long for this problem. So string or character array must be used.

This problem can solved in many ways Big Integer, FFT, Grade School etc. But I have implemented lattice multiplication / Chinese multiplication to solve this problem.

Code Explanation:

The code below requires quite a bit of polish to understand easily ( A lot other post require the same. Maybe I will update this post sometimes in future or not. ).

This code is not quite space efficient. I have used several arrays to make it easy to understand but all of the tasks below can be done using the large array. Also the running time can further be improved to $O(m*n)$ instead of $O(n^2)$ . Where, m and n are length of two arrays and they may not be equal in size.

I have provided some graphical representations below to make it easier to understand.

This is an example of how the multiplication works in this code. As mentioned above the process can be sped up using rectangular matrix instead of square if the length is not equal.

This is a representation of how the table / square matrix is filled for further processing.

Multiplication starts with the last character of string 1 and proceeds to first character. For string 2 multiplication starts from the first character till last character. This way each character from string 1 and string 2 is first converted to a digit, then they are multiplied. If the result is two digits it is divided by 10.

The remainder is written as the lower left portion ( indicated by lower in the structure ) and the quotient is written as the upper left portion ( indicated by upper in the structure ).

lattice multiplication structure traversal

This is graphical representation of how the structure is traversed. If you have trouble understanding how the recursive function traversing the structure, then take a look at UVA problem 264 – Count the Cantor Solution. The traversal is somewhat similar to that and I have provided explanation int that post.

Rest is explained in the code comments.

More Inputs of This Problem on uDebug.

Input:

12
12
2
222222222222222222222222

Output:

144
444444444444444444444444

Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   Lattice Multiplication.
 * Technique: High precision large number multiplication.
 *            Structure array representing upper left and
 *            and lower right corner in single cell.
 */

#include<stdio.h>
#include<string.h>


#define M 260

int N;


// Assuming both strings are of same length.
struct multiplicationTable{
    int upper;
    int lower;
};
struct multiplicationTable node[M][M];



static char string1[M];
static char string2[M];



// stores the diagonal sums;
int sum;

// decides whether to get the upper or lower
// value based on even or odd.
int m;


// Add diagonals.
int recursiveAdder( int i, int j ){

    // Termination condition.
    if( j < 0 || i >= N )
        return sum;

    int val;


    // Whether to get the upper left corner or
    // the lower right corner.
    if( m % 2 ){
        val = node[i][j].upper;
        j = j - 1;
    }
    else{
        val = node[i][j].lower;
        i = i + 1;
    }
    ++m;


    // store the sum of the whole diagonal.
    sum = sum + val;


    // recursively visit all row ans column
    // diagonally ( at least on pen and paper format ).
    // actually moves more like the snake in the snakes game.
    recursiveAdder(i,j);

    return sum;
}


// Debug.
// Print the matrix showing the multiplications.
// Please note left and right directions may be different.
void printMultiplicationMatrix(){

    printf("\n\n");
    for( int i = 0; i < N; ++i ){
        for( int j = N - 1; j >= 0; --j )
            printf("%d,%d, ", node[i][j].upper, node[i][j].lower );
        printf("\n");
    }

}







int main(){

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);


    while( gets(string1) ){
        gets(string2);

        int len1 = strlen(string1);
        int len2 = strlen(string2);

        // Fix length if both string are not equal size.
        // Adding leading zeros to smaller string.
        if( len1 > len2 ){
            N = len1;

            int shiftWidth = len1 - len2;

            for( int i = len1 - 1; i >= 0; --i )
                string2[i + shiftWidth] = string2[i];

            for(int j = 0; j < shiftWidth; ++j)
                string2[j] = '0';

        }
        else if(len2 > len1){
            N = len2;

            int shiftWidth = len2 - len1;

            for( int i = len2 - 1; i >= 0; --i )
                string1[i + shiftWidth] = string1[i];

            for(int j = 0; j < shiftWidth; ++j)
                string1[j] = '0';

        }
        else N = len1;


        //printf("%s \n%s \n", string1, string2);


        int k = N - 1;


        // Multiply the numbers digit by digit and set in the lattice.
        for( int i = 0; string2[i]; ++i ){
            for( int j = 0; string2[j]; ++j ){

                int num1 = string1[k] - '0';
                int num2 = string2[j] - '0';

                int multiply = num1 * num2;

                node[j][k].upper = multiply / 10;
                node[j][k].lower = multiply % 10;

            }
            --k;
        }

        //printMultiplicationMatrix();


        // Lattice is divided into two parts upper left half and
        // lower right half.


        // result of upper half
        int upperHalfResult[N];

        // Add upper half
        int i = N - 1;
        for(; i >= 0; --i){
            sum = 0;
            m = 1;
            upperHalfResult[i] = recursiveAdder(0, i);
        }


        // result of upper half
        int lowerHalfResult[N];

        // Add upper half
        i = 0;
        for(; i < N; ++i){
            sum = 0;
            m = 0;
            lowerHalfResult[i] = recursiveAdder(i, N - 1);
        }



        // Combine upper and lower left half to a single array to fix addition
        // problems.
        int combinedRawResult[N + N];
        i = 0;
        for(; i < N; ++i )
            combinedRawResult[i] = upperHalfResult[i];
        for(k = 0; i < N + N; ++i, ++k )
            combinedRawResult[i] = lowerHalfResult[k];



        // If a cell has more than 9 then it should be added to the next cell.
        for( int i = N + N - 1; i >= 0; --i ){

            if( combinedRawResult[i] > 9 ){
                combinedRawResult[i - 1] = combinedRawResult[i - 1] + combinedRawResult[i] / 10;
                combinedRawResult[i] = combinedRawResult[i] % 10;
            }

        }


        // Discard leading zeros.
        for(i = 0; i < N + N; ++i)
            if(combinedRawResult[i]) break;


        // print if the result can be printed or its zero.
        bool zero = true;
        for(; i < N + N; ++i){
            printf("%d", combinedRawResult[i]);
            zero = false;
        }

        // If the result is zero.
        if( zero )
            printf("0");

        printf("\n");



    }

    return 0;
}

UVA Problem 11988 – Broken Keyboard (a.k.a. Beiju Text) Solution

Posted on November 6, 2015November 6, 2015 by quickgrid

UVA Problem 11988 – Broken Keyboard (a.k.a. Beiju Text) Solution:

Click here to go to this problem in uva Online Judge.

Solving Technique:

The input may be classified into three things. One is append to beginning represented with ‘[‘, another is append to end represented with ‘]’ and the other types any other character except above mentioned. The other character are appended to the next position of last inserted character.

So task is move all characters following ‘[‘ to beginning until ‘]’ is found or end of string is reached. Similar logic applies to ‘]’ character. Also it is a recursive definition, keep applying this logic for all the following third brackets.

Other ideas:

Some other ideas to solve this problem can be, formatting the input to remove useless brackets then create a tree from inputs and perform in-order traversal to get the result. Another idea is create a linked list of strings.

Code Explanation:

I may later ( takes quite bit of time to create graphics ) provide a graphical representation of inserting in the doubly linked list ( 2nd code ). Meanwhile I provided a commented version ( 2nd code ) to make it a little easier to understand.

Here I have provided two codes. Both are linked list implementations. First one is singly linked list with no tail pointer( rather inefficient although I try to reduce some complexity by Boolean flag checking to reduce traversing the list to find tail pointer ). It is not able to keep track of tail pointer efficiently. Need to do some traversing ( some times almost the whole linked list ) to find the tail pointer.

The second implementation is doubly linked list with tail node as the tail pointer. The tail pointer has character has 0 which is ASCII decimal code for NULL character. I use this to stop printing otherwise a space character is printed at the end of output.

More Inputs of This Problem on uDebug.

Input:

This_is_a_[Beiju]_text
[[]][][]Happy_Birthday_to_Tsinghua_University

Output:

BeijuThis_is_a__text
Happy_Birthday_to_Tsinghua_University

Code Singly Linked list Without Tail:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 11988 - broken keyboard
 * Technique: Singly Linked List with no
 *            tail Pointer(slow).
 */

#include<stdio.h>
#include<string.h>


#define N 100000

static char input[N];


struct vertex{
    char c;
    struct vertex* next;
};

typedef struct vertex node;


node* insertNode(node* n, char c){

    node* temp = new node();
    temp->c = c;
    temp->next = n->next;
    n->next = temp;

    return temp;
}


void printList( node* dummy ){

    node* tmp = dummy;

    while( tmp = tmp->next )
        putchar( tmp->c );

    printf("\n");
}


int main(){

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);


    while( gets(input) ){

        node* dummy = new node();
        dummy->next = NULL;
        node* cur = dummy;


        node* tail = dummy;

        bool rightopen = false;

        for(int i = 0; input[i]; ++i){

            if( input[i] == '[' ){
                cur = dummy;
                rightopen = true;
                continue;
            }
            if( input[i] == ']' ){
                rightopen = false;

                node *tmp = tail;

                while( tmp->next != NULL )
                    tmp = tmp->next;

                tail = cur = tmp;
                continue;
            }

            cur = insertNode(cur, input[i] );
            if( !rightopen )
                tail = cur;
        }

        printList( dummy );

    }


    return 0;
}

Code Doubly Linked list With Tail Pointer:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 11988 - broken keyboard
 * Technique: Doubly Linked List with
 *            dummy tail node as Pointer.
 */

#include<stdio.h>
#include<string.h>


#define N 100000


static char input[N];



// Doubly linked list.
struct vertex{
    char c;
    struct vertex* next;
    struct vertex* prev;
};
typedef struct vertex node;



node* insertNode(node* n, char c){

    // Create the new node to hold current character.
    node* temp = new node();
    temp->c = c;


    // Create forward connection from this created node
    // to the next node of passed in node (n).
    // Also create backward connection from the passed
    // in node to current node.
    temp->next = n->next;
    n->next->prev = temp;


    // Create forward connection from passed in node (n) to the
    // newly created node (temp).
    // Also create backward connection from created node to the
    // passed in node.
    n->next = temp;
    temp->prev = n;


    // return the pointer to the current node.
    return temp;
}



void printList( node* dummy ){

    // Dummy (head) is not a part of output.
    node* tmp = dummy->next;


    // Since I use tail pointer, check if its tail.
    while( tmp->c ){
        putchar( tmp->c );
        tmp = tmp->next;
    }

    printf("\n");
}



int main(){

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);


    while( gets(input) ){

        // Dummy node is just to keep track of beginning.
        // It does not contain any input character.
        // Tail is used to insert before the last node.
        // Tail is also another dummy node keeps track of
        // the end.
        node* dummy = new node();
        node* tail = new node();


        // NULL may not be necessary since I use tail character
        // checking to stop printing.
        tail->prev = dummy;
        dummy->next = tail;
        tail->next = NULL;
        dummy->prev = NULL;


        // Set current node to dummy (beginning). Set tail
        // to NULL character equivalent ASCII value.
        node* cur = dummy;
        tail->c = 0;


        for(int i = 0; input[i]; ++i){

            // Update node pointer to beginning based on bracket.
            // If not bracket use previous pointer location.
            if( input[i] == '[' ){
                cur = dummy;
                continue;
            }
            if( input[i] == ']' ){
                cur = tail->prev;
                continue;
            }

            cur = insertNode(cur, input[i] );
        }


        // Print output characters one by one.
        printList( dummy );

    }


    return 0;
}

Multi Digit Subtraction without Negative Checking in 8086 Assembly Language

Posted on November 1, 2015 by quickgrid

Explanation:

This code preforms subtraction between two double digit numbers and prints their result. Note this works only if the digits of first number is bigger than second number. It doesn’t handle the exception that result can be negative.

Code:

;
; Author:  Asif Ahmed
; Site:    https://quickgrid.wordpress.com
; Comment: Semicolon means comment.
;
                                         
                                         
                                         
org 100h
     
.model small        
            
.stack 200h            
            
.data     
            
    
    msg1 db 'Enter first number: ', '$'
    msg2 db 'Enter first number: ', '$'
    msg3 db 'The output is: ', '$'
    crlf db 0dh, 0ah, '$'
    
    
    num1digit1 db ?
    num1digit2 db ?            
    num2digit1 db ?        
    num2digit2 db ?
                       
    
                       
            
.code        
.startup     
    
    
    ; Show prompt for inputting first number
             
    mov ah, 9
    lea dx, msg1
    int 21h         
    
     
                                                         
                                                         
    ; Take input of the first digit for the first number         
    
    mov ah, 1
    int 21h
    mov num1digit1, al
    sub num1digit1, 30h
                
    
    
    ; Take input of the second digit for the first number                   
                       
    mov ah, 1
    int 21h
    mov num1digit2, al
    sub num1digit2, 30h          
                       
                               
                               
                               
    ; Move cursor to a new line                       
             
    mov ah, 9
    lea dx, crlf
    int 21h
             
                               
                               
    
    ; Prompt for input of second number    
        
    mov ah, 9
    lea dx, msg2
    int 21h
    
                               
                               
    
    ; Take input of the first digit for the second number
    
    mov ah, 1
    int 21h
    mov num2digit1, al
    sub num2digit1, 30h
                                    
                                    
                                    
    
    ; Take input of the second digit for the second number
        
    mov ah, 1
    int 21h
    mov num2digit2, al
    sub num2digit2, 30h
     
        
                       
    ; Move cursor to new line
             
    mov ah, 9
    lea dx, crlf
    int 21h
                       
                       
    ; show output message
                
    mov ah, 9
    lea dx, msg3
    int 21h     
    
    
    ;Print the first result digit
    
    mov ah, 2
    mov cl, num1digit1
    sub cl, num2digit1
    mov dl, cl
    add dl, 30h    
    int 21h
        
        
        
    ;Print the second result digit    
   
    mov ah, 2
    mov cl, num1digit2
    sub cl, num2digit2
    mov dl, cl
    add dl, 30h
    int 21h  
    
                    
     
.exit

Simple Polynomial data structure and Calculator for single variable

Posted on November 1, 2015November 6, 2015 by quickgrid

Explanation:

The first code takes an integer for the value of the variable and the next one takes a double for the value of variable and produces value of the function.

I have commented the second code to make it easy. Pun intended on lines 144 to 147.

Calculates an equation with given value of the variable. If the equation is,

$f(x) = -50x^{-3} +3x -40x^2 +10x^{-5} -7x^{10}$

then for,

$x = -3, \ f(x) = -413710.189300 \\ x = -2, \ f(x) = -7328.062500 \\ x = -1, \ f(x) = -10.000000 \\ x = 0, \ \ \ f(x) = \ \ \ Undefined \\ x = 1, \ \ \ f(x) = -84.000000 \\ x = 2, \ \ \ f(x) = -7327.937500 \\ x = 3, \ \ \ f(x) = -413695.810700 \\$

(Pease Test this code before using, I haven’t done much testing). Check against this site. To use this from console comment freopen lines. Otherwise make two txt files named input and output in the same directory as the cpp file and follow the given equation input format.

Input:

-50x^-3 +3x^+1 -40x^+2 +10x^-5 -7x^+10
0
y
-3
y
-2
y
-1
y
0
y
1
y
2
y
3
n

Output:

-50x^-3 +3x^+1 -40x^+2 +10x^-5 -7x^+10 
Calculate value of Equation for given value (y/n)?
Enter value for the variable.
>>	 -413710.189300
Calculate value of Equation for given value (y/n)?
Enter value for the variable.
>>	 -7328.062500
Calculate value of Equation for given value (y/n)?
Enter value for the variable.
>>	 -10.000000
Calculate value of Equation for given value (y/n)?
Enter value for the variable.
Sorry Try something different
Calculate value of Equation for given value (y/n)?
Enter value for the variable.
>>	 -84.000000
Calculate value of Equation for given value (y/n)?
Enter value for the variable.
>>	 -7327.937500
Calculate value of Equation for given value (y/n)?
Enter value for the variable.
>>	 -413695.810700
Calculate value of Equation for given value (y/n)?
Exiting...

Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   Simple Polynomial data structure and
 *            Calculator for single variable.
 */

#include<stdio.h>
#include<string.h>
#include<math.h>


#define N 512


char input[N];


struct PolynomialEquation{

    char sign;
    char signExponent;
    int exponent;
    char variable;
    int constant;

    struct PolynomialEquation *next;
};
typedef struct PolynomialEquation node;



node* insertNode(node* current, char sign, int constant, char variable, char signExponent, int exponent){

    node* temp = new node();

    temp->sign = sign;
    temp->signExponent = signExponent;
    temp->exponent = exponent;
    temp->variable = variable;
    temp->constant = constant;

    temp->next = NULL;
    current->next = temp;
    current = temp;

    return current;
}


void printEquation(node* dummy){
    node* tmp = dummy->next;
    while( tmp != NULL ){
        printf("%c%d%c^%c%d ", tmp->sign, tmp->constant, tmp->variable, tmp->signExponent, tmp->exponent);
        tmp = tmp->next;
    }
    printf("\n");
}


void calculateEquation(node* dummy, int var){

    double sum = 0;
    bool calculable;


    node* tmp = dummy->next;
    while( tmp != NULL ){

        double constantValue = 0, variableValue = 0;
        calculable = true;


        constantValue = tmp->constant;
        if(tmp->sign == '-')
            constantValue *= -1;


        variableValue = pow(var, tmp->exponent);
        if(tmp->signExponent == '-'){
            if(variableValue)
                variableValue = (double) 1 / variableValue;
            else
                calculable = false;
        }


        sum = sum + variableValue * constantValue;
        tmp = tmp->next;


        if(!calculable){
            printf("Sorry Try something different\n");
            break;
        }

    }

    if(calculable)
        printf(">>\t %f\n", sum);

}


int main(){

    // Comment these lines to do I/O operation in console.
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);



    char sign;
    char signExponent;
    int exponent;
    char variable;
    int constant;



    node* dummy = new node();
    dummy->variable = '$';
    node* current = dummy;


    while( scanf("%c%d%c%*c%c%d", &sign, &constant, &variable, &signExponent, &exponent ) == 5){
        getchar();
        current = insertNode(current, sign, constant, variable, signExponent, exponent);
    }

    printEquation(dummy);


    while(1){
        printf("Calculate value of Equation for given value (y/n)?\n");

        char choice = getchar();

        if( choice == 'y' ){
            printf("Enter value for the variable.\n");

            int variableValue;
            scanf("%d", &variableValue);
            getchar();

            calculateEquation(dummy, variableValue);
        }else{
            printf("Exiting...\n");
            break;
        }
    }

    return 0;
}

Working with float numbers:

If the equation is,

$f(x) = - 4x^{2} - 4x - 9$

Input:

+4x^+2 -4x^+1 -9x^+0
0
y
5
y
2.5
y
1.25
y
1.875
n

Output:

+4x^+2 -4x^+1 -9x^+0 
Calculate value of Equation for given value (y/n)?
Enter value for the variable:
>>	 71.000000
Calculate value of Equation for given value (y/n)?
Enter value for the variable:
>>	 6.000000
Calculate value of Equation for given value (y/n)?
Enter value for the variable:
>>	 -7.750000
Calculate value of Equation for given value (y/n)?
Enter value for the variable:
>>	 -2.437500
Calculate value of Equation for given value (y/n)?
Exiting...

Code for float:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   Simple Polynomial data structure and
 *            Calculator with single variable.
 */

#include<stdio.h>
#include<string.h>
#include<math.h>


#define N 512


char input[N];


struct PolynomialEquation{

    char sign;
    char signExponent;
    int exponent;
    char variable;
    int constant;

    struct PolynomialEquation *next;
};
typedef struct PolynomialEquation node;



node* insertNode(node* current, char sign, int constant, char variable, char signExponent, int exponent){

    node* temp = new node();


    temp->sign = sign;
    temp->signExponent = signExponent;
    temp->exponent = exponent;
    temp->variable = variable;
    temp->constant = constant;


    temp->next = NULL;
    current->next = temp;
    current = temp;


    return current;
}


void printEquation(node* dummy){

    // dummy is just an empty node to keep track of front of equation.
    // It is not part of equation. Equation starts after dummy node.
    node* tmp = dummy->next;

    // Print the equation term by term.
    while( tmp != NULL ){
        printf("%c%d%c^%c%d ", tmp->sign, tmp->constant, tmp->variable, tmp->signExponent, tmp->exponent);
        tmp = tmp->next;
    }
    printf("\n");

}


void calculateEquation(node* dummy, double var){

    double sum = 0;
    bool calculable;


    // dummy->next because dummy node is not a part of the equation.
    node* tmp = dummy->next;

    while( tmp != NULL ){

        double constantValue = 0, variableValue = 0;
        calculable = true;

        // make constant negative if the sign is negative.
        constantValue = tmp->constant;
        if(tmp->sign == '-')
            constantValue *= -1;


        // calculate the value of the variable with given exponent.
        variableValue = pow(var, tmp->exponent);
        if(tmp->signExponent == '-'){
            if(variableValue)
                variableValue = (double) 1 / variableValue;
            else
                calculable = false;
        }


        // multiply the calculated value of variable with the constant.
        sum = sum + variableValue * constantValue;

        // calculate the next term of the equation.
        tmp = tmp->next;


        // If not calculable. Ex: divide by zero. then print this.
        if(!calculable){
            printf("Sorry Try something different\n");
            break;
        }

    }

    // print the result.
    if(calculable)
        printf(">>\t %f\n", sum);

}


int main(){

    // Comment these lines to do I/O operation in console.
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);



    char sign;
    char signExponent;
    int exponent;
    char variable;
    int constant;


    // Dummy node to make insertion code simpler.
    node* dummy = new node();
    dummy->variable = '$';
    node* current = dummy;


    // Take input of equation term by term.
    // If
    //     taking input from console stop input using null terminator ( ctrl + z ).
    // Else
    //     when taking input from file enter a 0 in a line by itself to stop input.
    while( scanf("%c%d%c%*c%c%d", &sign, &constant, &variable, &signExponent, &exponent ) == 5){
        getchar();
        current = insertNode(current, sign, constant, variable, signExponent, exponent);
    }

    // print the
    printEquation(dummy);


    // Enter different values for the variable to get the value of function.
    while(1){
        printf("Calculate value of Equation for given value (y/n)?\n");

        char choice = getchar();

        if( choice == 'y' ){
            printf("Enter value for the variable:\n");

            double variableValue;
            scanf("%lf", &variableValue);
            getchar();

            calculateEquation(dummy, variableValue);
        }else{
            printf("Exiting...\n");
            break;
        }
    }

    return 0;
}

Code:

Unnecessary Complex Code:

Share this:

Visual Explanation:

Example:

Code:

Share this:

Code:

Share this:

Visualization:

Code:

Share this:

Code Fibonacci Generation with Golden ratio:

Share this:

The brute force way:

Trying to Come up with a Closed Form Expression:

Input – Values in the Row(Last three numbers bracketed) – Sum

Trying to come up with a Brute Force Approach:

Generating Solution From the Output:

Generating Solution based on First Number of Last Three:

Formula Generate sequence sum, first number & sum Code:

Reduced Formula Code:

Brute Force Code( Won’t be Accepted ):

Share this:

Code:

Share this:

Other ideas:

Code Explanation:

Code Singly Linked list Without Tail:

Code Doubly Linked list With Tail Pointer:

Share this:

Explanation:

Code:

Share this:

Explanation:

then for,

Input:

Output:

Code:

Working with float numbers:

Input:

Output:

Code for float:

Share this: