C,C++/JAVA/BASH/ASM ARENA

वह प्रदीप जो दीख रहा है झिलमिल दूर नही है थक कर बैठ गये क्या भाई मन्जिल दूर नही है चिन्गारी बन गयी लहू की बून्द गिरी जो पग से चमक रहे पीछे मुड देखो चरण-चिनह जगमग से बाकी होश तभी तक, जब तक जलता तूर नही है थक कर बैठ गये क्या भाई मन्जिल दूर नही है अपनी हड्डी की मशाल से हृदय चीरते तम का, सारी रात चले तुम दुख झेलते कुलिश का। एक खेय है शेष, किसी विध पार उसे कर जाओ; वह देखो, उस पार चमकता है मन्दिर प्रियतम का। आकर इतना पास फिरे, वह सच्चा शूर नहीं है; थककर बैठ गये क्या भाई! मंज़िल दूर नहीं है। दिशा दीप्त हो उठी प्राप्त कर पुण्य-प्रकाश तुम्हारा, लिखा जा चुका अनल-अक्षरों में इतिहास तुम्हारा। जिस मिट्टी ने लहू पिया, वह फूल खिलाएगी ही, अम्बर पर घन बन छाएगा ही उच्छ्वास तुम्हारा। और अधिक ले जाँच, देवता इतन क्रूर नहीं है। थककर बैठ गये क्या भाई! मंज़िल दूर नहीं है।

Project Euler Problem 57 – Square root convergents March 22, 2013

Filed under: Project Euler — whoami @ 11:33
Tags: , , , ,

It is possible to show that the square root of two can be expressed as an infinite continued fraction.

√ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + … ))) = 1.414213…

By expanding this for the first four iterations, we get:

1 + 1/2 = 3/2 = 1.5
1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666…
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379…

The next three expansions are 99/70, 239/169, and 577/408, but the eighth expansion, 1393/985, is the first example where the number of digits in the numerator exceeds the number of digits in the denominator.

In the first one-thousand expansions, how many fractions contain a numerator with more digits than denominator?

Euler57

Advertisements
 

Project Euler Problem 204 Generalised Hamming Numbers March 21, 2013

Filed under: Project Euler — whoami @ 08:46
Tags: , , , ,

A Hamming number is a positive number which has no prime factor larger than 5.
So the first few Hamming numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15.
There are 1105 Hamming numbers not exceeding 108.

We will call a positive number a generalised Hamming number of type n, if it has no prime factor larger than n.
Hence the Hamming numbers are the generalised Hamming numbers of type 5.

How many generalised Hamming numbers of type 100 are there which don’t exceed 10^9?

Hint: Generate prime number less than 100. Check for all the number in range 1-10^9, whether all prime number <100 divides them totally to get final remaining number as 1. Is this happens for particular number then add it to your list otherwise don’t add the number to the list.

euler204

 

Project Euler Problem 206 Concealed Square March 20, 2013

Filed under: Project Euler — whoami @ 12:41

Find the unique positive integer whose square has the form 1_2_3_4_5_6_7_8_9_0,
where each “_” is a single digit.

My solution..PROJECT EULER PROBLEM 206 – Concealed Square

 

My misconception about Compound assignment operators in C,C++ March 18, 2013

Filed under: Uncategorized — whoami @ 09:41
Tags: , , ,

Today i got cleared of a very big misconception about Compound assignment operators.

I had wrongly understood statements like

A -=b+c as A=A-b+cBut correct is A -=b+c is same as A = A – (b+c)

More explanation can be find here

I have built this wrong concept because in elementary C books there was rarely mentioning of three variables for compound assignment operator examples. Like

The last example(bottom) below i never came through 😦

expression

evaluation

value += increase;

value = value + increase;

a -= 5;

a = a - 5;

a /= b;

a = a / b;

price *= units + 1;

price = price * (units + 1)

 

Facebook Hacker Cup 2013 Qualification round Problem 3 – Find the Min January 27, 2013

Filed under: Facebook Hacker Cup — whoami @ 13:28
Tags: ,

Find the Min

Though i got the output for the given input file, my below solution gave wrong results within 6 minutes time duration mainly because of not using “long long int” datatype for creating pseudonumbers.
It was because of the data overflow.

After changing the datatypes, got the positive answers(though it has not been tested as test results are not known).

I am just publishing my solution for my further reference( as i could not submit in the contest).

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string.h>
#include <queue>
using namespace std;

long long int originals[1000009];
long long int generated_numbers[1000009];
long long int ans[1000009];

int main()
{
    //freopen("find_the_min.txt","r",stdin);
    freopen("find_the_min2.txt","r",stdin);
    //freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);

    int T,testcase=0;
    scanf("%d",&T);
    while(T--)
    {
        int n,k;
        scanf("%d%d",&n,&k);

        int a,b,c,r;
        scanf("%d%d%d%d",&a,&b,&c,&r);

        long long int m[k];

        m[0]=a;

        for(int i=1;i<k;i++)
        {
            long long int tmp1=b%r;
            long long int tmp2=m[i-1]%r;
            long long int ltmp=tmp1*tmp2;
            ltmp=ltmp%r;
            long long int tmp3=ltmp;
            long long int tmp4=c%r;
            long long int final=(tmp3+tmp4)%r;
            m[i]=final;
        }

        /*keep two sorted arrays, whose values can be used for each of
        the indexes <n
        */

        //originals
        for(int i=0;i<k;i++)
        {
            originals[i]=m[i];
        }
        sort(originals, originals+k);

        //generated
        int count=0;
        for(int i=0;i<k&&count<k;i++)
        {
            if(i==0)
            {
                if(originals[i]>0)
                {
                    for(long long int l=0;l<originals[i]&&count<k;l++)
                    {
                        generated_numbers[count++]=l;
                    }
                }
            }
            else
            {
                if(originals[i]-originals[i-1] > 1)
                {
                    int times=originals[i]-originals[i-1]-1;
                    long long int start=originals[i-1]+1;
                    for(int l=0;l<times&&count<k;l++,start++)
                    {
                        generated_numbers[count++] = start;
                    }
                }
            }

        }

        if(count < k )
        {
            long long int start=originals[k-1]+1;
            while(count < k)
            {
                generated_numbers[count++]=start;
                start++;
            }
        }

        deque<long long int>dq;
        for(int i=0;i<k;i++)
        {
            dq.push_back(m[i]);
            ans[i]=m[i];
        }
        set<long long int>st;st.clear();
        for(int i=0;i<count;i++)
        {
            st.insert(generated_numbers[i]);
        }

        int total_iterations=0;
        int total=k;
        while(total_iterations <2*k+2 )
        {
            ++total_iterations;
            long long int item=dq.front();
            dq.pop_front();

            std::set<long long int>::iterator it;
            if(st.size()>=1 )
            {
                long long int item_to_insert_in_dq = *(st.begin());
                dq.push_back(item_to_insert_in_dq);
                ans[total++] = item_to_insert_in_dq;
                st.erase (st.begin());
            }

            if(total_iterations <= k)
            {
                int flag=1;
                for(int i=total_iterations,j=0;j<k-1;i++,j++)
                {
                    if(item == ans[i])
                    {
                        flag=0;
                        break;
                    }
                }

                if(flag==1)
                {
                    st.insert(item);
                }
            }
            else
            {
                st.insert(item);
            }

            if(total_iterations == n) break;
        }
            printf("Case #%d: ",++testcase);

            if( (n-k) %(k+1) == 0)
            {
                printf("%lld\n",ans[k+k]);
            }
            else
            {
                printf("%lld\n",ans[k+((n-k)%(k+1))-1]);
            }

    }

    return 0;
}

🙂

Please donot use this code to submit in the running contest. It will not help in long run…

 

Check your pointer skills. January 4, 2013

Filed under: Uncategorized — whoami @ 11:47
Tags: , , , ,

Good Evening !!!

Explain the following :-

1. int (*(*foo)(void ))[3]

2.char *const argv[]

3. char * const *argv

4. void (*p[10]) (void (*)() )

Things that you might know well:-

1. const char*

2. char* const

3. const char* const

4. const *char ->tricky

5. char const * -> similar as one of the above(guess which one?)

🙂

 

Apn ( access point name ) in message compression – rfc 1035 ( explained in 3gpp 23.003 rel9) October 29, 2012

When we are getting APN name in message from UE( Mobile ), the buffer contains apn ( e.g. myoperator.com  ) encoded in format defined in rfc 1035 . 3GPP spec 23.003( rel9) explains about this rfc. To convert this encoded apn back to readable apn name( e.g. myoperator.com) , we need to write our own routine.

Example of the encoded APN explained in rfc 1035 [page 30]

For example, a datagram might need to use the domain names F.ISI.ARPA,
FOO.F.ISI.ARPA, ARPA, and the root.  Ignoring the other fields of the
message, these domain names might be represented as:

       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    20 |           1           |           F           |
       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    22 |           3           |           I           |
       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    24 |           S           |           I           |
       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    26 |           4           |           A           |
       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    28 |           R           |           P           |
       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    30 |           A           |           0           |
       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    40 |           3           |           F           |
       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    42 |           O           |           O           |
       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    44 | 1  1|                20                       |
       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    64 | 1  1|                26                       |
       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
    92 |           0           |                       |
       +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
The domain name for F.ISI.ARPA is shown at offset 20.  The domain name
FOO.F.ISI.ARPA is shown at offset 40; this definition uses a pointer to
concatenate a label for FOO to the previously defined F.ISI.ARPA.  The
domain name ARPA is defined at offset 64 using a pointer to the ARPA
component of the name F.ISI.ARPA at 20; note that this pointer relies on
ARPA being the last label in the string at 20.  The root domain name is 
defined by a single octet of zeros at 92; the root domain name has no
labels.