Archive

Posts Tagged ‘c’

Project euler problem 20


This problem is very simple one liner in python.

n! means n × (n − 1) × … × 3 × 2 × 1

For example, 10! = 10 × 9 × … × 3 × 2 × 1 = 3628800,
and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

Find the sum of the digits in the number 100!

import math
print sum([int(x) for x in  str(math.factorial(100))])

Answer: 648

real 0m0.164s
user 0m0.031s
sys 0m0.108s

Project Euler: Problem 16: Find the sum of all the digits in 2 power 1000


This problem is simple and straight forward. I’ve used a character buffer to store the powers of 2 for each iteration starting from 1 to 1000.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char *strrev(char *str)
{
      char *p1, *p2;

      if (! str || ! *str)
            return str;
      for (p1 = str, p2 = str + strlen(str) - 1; p2 > p1; ++p1, --p2)
      {
            *p1 ^= *p2;
            *p2 ^= *p1;
            *p1 ^= *p2;
      }
      return str;
}
int main(void)
{
    char *digits = (char *)malloc(sizeof(char) * 2000);
    memset(digits, 0, 2000);
    digits[0] = '1';
    unsigned int carry = 0;
    int i, j;
    for (i = 0; i < 1000; i++) {
        carry = 0;
        for (j = 0; j < strlen(digits); j++) {
            int m = (digits[j] - '0') * 2 + carry;
            carry = (m / 10) % 10;
            digits[j] = (m % 10) + '0';
        }
        if (carry)
            digits[j] = carry + '0';
    }
    strrev(digits);
    printf("2 power 1000 is: %s\n", digits);
    carry = 0;
    for (int i = 0; i < strlen(digits); i++)
        carry += (digits[i] - '0');
    printf("Answer: %d\n", carry);
}

2 power 1000 is:

10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376

Answer: 1366

real 0m0.085s
user 0m0.015s
sys 0m0.062s

One interesting thing to notice here is that the above same code can be written in python with in a single line using comprehensions as follows. 🙂


sum([int(n) for n in str(2**1000)])

>>> sum([int(n) for n in str(2**1000)])
1366

Categories: Programming Tags: , ,

Program to convert one endian ness to another


Here is the program to convert from given endian ness to other endian ness. If the given endian ness is little it converts to big endian and vice versa.
This code has been written keeping in mind sizeof(int) = 4 Bytes.

#include <stdio.h>
 
int main(void)
{
    int i = 0x12345678;
    printf("Before 0x%x\n", i);
    int p = 0;
    p |= ((0xff & i) << 24);
    p |= ((((0xff << 8) & i) >> 8) << 16);
    p |= ((((0xff << 16) & i) >> 16) << 8);
    p |= ((((0xff << 24) & i) >> 24));
    printf("After 0x%x\n", p);
    return 0;
}

Thanks for the comments. As per the suggestions adding some more explanation.

Here the following code tells you whether you have LSB representation or MSB representation

#include <stdio.h>
 
int main(void)
{
    int i = 0x12345678;
    char *r;
    r = &i;
    printf("Internal storage representation: %x%x%x%x\n", r[0], r[1], r[2],  r[3]);
    return 0;
}

After you run the above code if you get the prints as 78563412 then you have LSB based representation. Else this code prints 12345678 then you have MSB based representation.

So, if you quickly see the above two representations for i = 0x12345678; For any byte sequence p1 p2 p3 p4 the other endian representation is p4 p3 p2 p1.
Hence for conversion for a 4 byte integers we need to take the last byte and place it in the appropriate 31 to 24 bit position.

ie., p |= ((0xff & i) << 24);

Now we need to take the bits from 9 to 16 (ie., second byte) and place them in 23 to 16 positions.

ie., p |= ((((0xff <> 8) << 16);

same applies for the next two bytes as well.

Thanks for reading the article.

Sorting is easy!!!


One of the most common questions in many interviews is the sorting techniques. There are many sorting techniques, I am going to explain some of them in the coming posts.

We will start off with, the basic and simplest of all the sorting techniques, Bubble sort

Bubble Sort

Method: Bubble sort compares two adjacent elements and swaps if the first element is greater than the second one. After every pass the largest element in that pass bubbles up to the last position.

Example:

suppose the array elements are

5  7  8  3  2

pass1:

5  7 8  3  2  (compare 5 & 7)  (No Exchange)

5  7  8 3  2  (compare 7 & 8 )  (No Exchange)

5  7 8 3 2  (compare 8 & 3)  (Exchange)

5  7 3 8 2 (compare 8 & 2)  (Exchange)

5  7 3  2  8    (End of the pass1, the largest element is in its corresponding position the array)

pass2:

5 7 3 2 8 (compare 5 & 7)  (No Exchange)

5  7 3 2 8 (compare 7 & 3)  (Exchange)

5 3 7 2 8 (compare 7 & 2)  (Exchange)

5  3 2 7 8 (End of the pass2, the largest element in the pass2 is bubbled up to its corresponding position)

pass 3:

5  3 2 7 8 (compare 5 & 3)  (Exchange)

3 5  2 7 8 (compare 5 & 2)  (Exchange)

3  2 5 7 8 (End of the pass3, the largest element in this pass is bubbled up to its corresponding position)

pass 4:

3  2 5 7 8 (compare 3 &2 ) (Exchange)

2 3 5 7 8 (End of the pass4, all elements sorted)

Algorithm

#include<stdio.h>
#include<conio.h>
int main(void)
{
int a[]={1,12,2,11,3},i,j,n=5,temp;
for(i=0;i<n-1;i++)
{
for(j=0;j<n-i-1;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
for(i=0;i<n;i++)
printf(“%d “,a[i]);
getch();
return 0;
}

compiled on: dev c++,  gcc, Turbo C

Analysis:

Worst Case: O(N2)        Average Case: O(N2)


Program to extract source code from comment lines


#include<stdio.h>
#include<conio.h>
void main()
{
FILE *p;
char ch=’a’,ch1;
int count=1;
clrscr();
p=fopen(“cfile.c”,”r”);//this is the demonstration of comment line
if(p==NULL)
{
printf(“File not found”);
exit(1);
}
while(ch!=EOF)
{
ch=fgetc(p);
if(ch==’\n’)
count++;
else if(ch=='”‘) {
while((ch=fgetc(p))!=’\n’);
count++;
}
else if(ch==’/’)
{
if((ch1=fgetc(p))==’/’)
{
printf(“\nComment no %d:”,count);
while((ch=fgetc(p))!=’\n’&&ch!=EOF)
printf(“%c”,ch);
count++;
printf(“\n”);
continue;
}
else if(ch1==’*’)
{
printf(“\nComment %d :”,count);
while(ch!=EOF)
{
if((ch=fgetc(p))==’*’)
{
ch1=fgetc(p);
if(ch1==’/’)
break;
else
{
printf(“%c%c”,ch,ch1);
continue;
}
}
else if(ch==’\n’)
count++;
printf(“%c”,ch);
}
printf(“\n”);
}
}
}
getch();
}

Compiled on: Turbo C, gcc

Description : Extracts the program source code with out the comment lines in the given source file

program to swap two numbers with out using temporary variable with in one line


#include <stdio.h>
#include <conio.h>
int main(void)
{
int a , b;
printf(“Enter two integers: “);
scanf(“%d%d”,&a,&b);
printf(“Before swapping: a=%d,b=%d\n”,a,b);
a=(a+b)-(b=a); //This is just one line
printf(“After swapping: a=%d,b=%d”,a,b);
getch();
return 0;
}
compiled on :gcc logic :simple and tricky
If you have any doubts please add a comment

program to swap two numbers with out using temporary variable


#include < stdio.h >
#include < conio.h >
int main(void)
{
int a,b,i,j;
clrscr();
printf(“Enter two integers: “);
scanf(“%d%d”,&a,&b);
printf(“a=%d,b=%d\n”,a,b);
for(i=0;i<sizeof(int)*8;i++)
{
if((a&(1<<i))^(b&(1<<i)))
{
a=a^(1<<i);
b=b^(1<<i);
}
}
printf(“a=%d,b=%d”,a,b);
getch();
return 0;
}