Evaluating a Polynomial

You are given a polynomial of degree n. The polynomial is of the form P(x) = anxn + an-1xn-1 + … + a0, where the ai‘s are the coefficients.  Given an integer x, write a program that will evaluate P(x).

SOLUTION:
#include<stdio.h> /* function to calculate power x^y */ int power(int x, int y){ int pow=1; while (y!=0){ pow*=x; y--; } return pow; }

int main() { int n, x; int a[10]; scanf("%d %d", &n, &x); int i, j, sum=0; for(i=n; i>=0; i--) { scanf("%d", &a[i]); } int temp=0; for(j=n; j>=0; j--) { temp=a[j]*power(x,j); sum=sum+temp; } printf("%d", sum); return 0; }

Largest sum of all contiguous subarrays

Lets take an example of an array {5,-3, 4}. Possible contiguous subarray combinations are {5}, {-3}, {4}, {5,-3}, {-3,4} and {5,-3,4}. Note that {5,4} is not a valid subarray as the indices of 5 and 4 are not continuous.

The contiguous subarray  {5,-3,4} has the largest sum 6.

Solution:

/* In general one would approach this problem by iterating for all possible start and end combinations which would make N*(N-1)/2 combinations. But instead of this one could solve this using pre-computation i.e, let us consider cur_max(i) is sum of maximum sum contiguous subarray ending at index i, then cur_max(i) is given by, cur_max(i) = max(cur_max(i-1)+val(i),val(i)) where val(i) is value at index i. Maximum sum subarray can be found by finding the maximum of all cur_max. By using the precomputed cur_max of i-1 we can compute cur_max of i. Hence the below logic becomes a optimal computation of largest sum contiguous subarray. */ #include<stdio.h> #define MAX 100 int main() { int size,input[MAX],i; scanf("%d",&size); for(i=0;i<size;i++){ scanf("%d",&input[i]); } //curr_max computes the largest contiguous maximum sum ending at cur_idx //max_so_far (global maxima)computes the largest contiguous maximum sum till the cur_idx long max_so_far = input[0]; long curr_max = input[0]; for (i = 1; i < size; i++){ curr_max = (input[i]>curr_max+input[i]) ? input[i] : curr_max+input[i]; max_so_far =(max_so_far>curr_max) ? max_so_far : curr_max; } printf("%ld",max_so_far); return 0; }

Find the depth of letters in a string

A string is given which has letters from English alphabet and parentheses. The depth of a letter is defined as the number of balanced parentheses it is surrounded by. Write a  C program to find the depth of each letter in the input string.

Explanation:

(a(b)((cd)e)f)g

g is at depth 0
a and f are at depth 1
b and e are at depth 2
c and d are at depth 3

Solution:

#include<stdio.h>
#include<string.h>
int main()
 {
  int a=0,i,set=0;
  char input[100];
  scanf("%s",input);
  for(i=0;input[i]!='\0';i++)
   {
    switch(input[i])
     {
        case '(':
                a++;
                break;
        case ')':
                a--;
                break;
        default :  
                printf("%d ",a);
                set = 1;
      }   
      
   }
  if(set==0)
     printf(" #");
  else
     printf("#");
  return 0;

}

Find whether two given strings are permutations of each other

Write a program to find whether two given strings are permutations of each other.  A string str1 is a permutation of str2 if all the characters in str1 appear the same number of times in str2 and str2 is of the same length as str1.

Solution:

#include<stdio.h> int main(){ int acount[128] = {0}, bcount[128] = {0}, c = 0; char a[100]; char b[100]; scanf("%s",a); scanf("%s",b); //now take every character from string 'a' and using ASCII value increment corresponding index in array 'acount' while (a[c] != '\0') { acount[(int)a[c]]++; c++; } c = 0; //now take every character from string 'b' and using ASCII value increment corresponding index in array 'bcount' while (b[c] != '\0') { bcount[(int)b[c]]++; c++; } for (c = 0; c < 128; c++) { //if any single character also mismatch then return no if (acount[c] != bcount[c]) { printf("no"); return 0; } } //satisfy criteria so return true printf("yes"); return 0; }

program to check if all the three points fall on one straight line

Given three points (x1, y1), (x2, y2) and (x3, y3) , write a program to check if all the three points fall on one straight line.

SOLUTION:

#include<stdio.h> int main() { int x1, x2, x3, y1, y2, y3; scanf("%d %d %d %d %d %d", &x1,&y1,&x2,&y2,&x3,&y3); float area; area=0.5*((x1*(y2-y3))+(x2*(y3-y1))+(x3*(y1-y2))); if(area==0) { printf("Yes"); } else { printf("No"); } return(0); }

C program that takes a positive number N and produces an output that is the product of its digits

Write a C program that takes a positive number N and produces an output that is the product of its digits.

Explanation:

Take number 657.

Answer expected : 6 * 5 * 7 = 210

Solution

#include<stdio.h> int main() { int a, test, c, product=1; scanf("%d", &a); test=a; while(a!=0) { c=a%10; product=product*c; a=a/10; }; printf("%d", product); return 0; }

find whether a given number (say x) is a “perfect number” or not.

Definition of Perfect number:

A perfect number is a positive integer that is equal to the sum of its proper positive divisors excluding the number itself. By this definition, 1 is not a perfect number.

Explanation:

Take number 6.

Proper positive divisors of 6 is 1,2,3 and their sum is 1+2+3=6.
So, 6 is a perfect number.

Solution

#include<stdio.h> int main() { int a, b; scanf("%d", &a); b=a; int sum=0, i; for(i=1; i<a; i++) { if((a%i)==0) { sum=sum+i; } } if(sum==b) printf("yes"); else printf("no"); return 0; }

Print Number of Perfect Squares Between two numbers

Write a program to find the number of perfect squares between given two numbers A and B (both inclusive). A number is called a perfect square if it can be written as x*x for some integer x.

Example 1:

Input: 3 17

Output: 3

Solution.

#include<stdio.h>

int main()

{

  int a, b;

scanf("%d%d", &a, &b);

 

int count=0;

int i, h;

for(i=1; i<=b; i++)

{

h=i*i;

if((a<=h)&&(b>=h))

count++;

}

  printf("%d", count);

  return 0;

}

Print elements of a matrix in spiral order

Write a program that reads an MxN matrix A and prints its elements in spiral order.

You should start from the element in the 0th row and 0th column in the matrix and proceed in a spiral order as shown below.

1→ 2 → 3 → 4                       

                      ↓

5 → 6 → 7 8

↑             ↓ ↓

9    10←11 12

↑              ↓

13←14←15←16

Output for the above matrix: 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

Solution:

#include<stdio.h> int main() { int A[5][5]; int B[25]; int M, N; int i,j; int cnt=0; int cnt1=0; int top, bot, right, left; scanf("%d%d",&M,&N); for(i=0; i<M; i++){ for(j=0; j<N; j++){ scanf("%d",&A[i][j]); } } top = 0; bot = M-1; left = 0; right = N-1; for(cnt1=1; cnt1 <= M/2 && cnt1 <= N/2; cnt1++){ for(i=left; i<= right; i++){ B[cnt++]= A[top][i]; } for(i=top+1;i<=bot;i++){ B[cnt++]= A[i][right]; } for(i=right-1; i>=left; i--){ B[cnt++]= A[bot][i]; } for(i=bot-1; i>=top+1; i--){ B[cnt++] = A[i][left]; } top++; bot--; left++; right--; } if(top==bot && left==right){ B[cnt++]=A[top][left]; } else if(top<bot){ for(i=top;i<=bot;i++){ B[cnt++]=A[i][left]; } } else if(left<right){ for(i=left; i<=right;i++){ B[cnt++]=A[top][i]; } } for(i=0;i<M*N-1;i++){ printf("%d ",B[i]); } printf("%d",B[i]); return 0; }