Showing posts with label C competitive coding. Show all posts
Showing posts with label C competitive coding. Show all posts

Project Euler #17: Number to Words | Hackerrank | Project Euler

 Number to Words


The numbers 1 to 5 written out in words are One, Two, Three, Four, Five 

First character of each word will be capital letter for example:
 104382426112 is 

One Hundred Four Billion Three Hundred Eighty Two Million Four Hundred Twenty Six Thousand One Hundred and Twelve

Given a number, you have to write it in words.

Input Format

The first line contains an integer T, i.e., number of test cases.
Next T lines will contain an integer N.

Constraints

1<=T<=10
0<=N<=10^2

Output Format

Print the values corresponding to each test case.

Sample Input

2
10
17

Sample Output

Ten 
Seventeen

Solution : Source (Hackerrank)


#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
char digits[20][10] = {"","One","Two","Three","Four",
"Five","Six","Seven","Eight","Nine","Ten","Eleven",
"Twelve","Thirteen","Fourteen",
"Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"};
char tens[11][10] =  {"","","Twenty","Thirty","Forty",
"Fifty","Sixty","Seventy","Eighty","Ninety"};

void word(int num){
    if(num/100)
        printf("%s Hundred ", digits[num/100]);
    if((num%100) < 20 && (num%100) > 0)
        printf("%s ",digits[num%100]);
    else if((num/10)%10){
        printf("%s ", tens[(num/10)%10]);
        if(num%10)
            printf("%s ", digits[num%10]);
    }
}

int main() {
    int t;
    scanf("%d", &t);
    while(t--){
        long long int num;
        scanf("%lld", &num);
        int tn = num / 1000000000000;
        int bn = (num / 1000000000) % 1000;
        int mn = (num / 1000000) % 1000;
        int th = (num / 1000) % 1000;
        int hd = num % 1000;
        //printf("%d %d %d %d %d\n", tn, bn, mn, th, hd);
        if((tn + bn + mn + th + hd) == 0)
            printf("Zero");
        if(tn){
            word(tn);
            printf("Trillion ");
        }
        if(bn){
            word(bn);
            printf("Billion ");
        }
        if(mn){
            word(mn);
            printf("Million ");
        }
        if(th){
            word(th);
            printf("Thousand ");
        }
        if(hd){
            word(hd);
        }
       printf("\n"); 
    }
    return 0;
}


You can also run it on an online IDE :


Your feedback are always welcome! If you have any doubt you 
can contact me or leave a comment!  
Happy Coding!! Cheers!!!




Project Euler #6: Sum square difference | Hackerrank | Project Euler

 

 Sum square difference 


The sum of the squares of the first ten natural numbers is, 1^2+2^2+...+10^2=385 . The square of the sum of the first ten natural numbers is, (1+2+...+10)^2 = 55^2 = 3025 . Hence the absolute difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025-385=2640.

Find the absolute difference between the sum of the squares of the first N natural numbers and the square of the sum.

Input Format

First line contains T that denotes the number of test cases. This is followed by T lines, each containing an integer, N.

Constraints

1<=T<=10^4

1<=N<=10^4

Output Format

Print the required answer for each test case.

Sample Input 0

2

3

10

Sample Output 0

22

2640


Explanation 0

For N=3 , (1+2+3)^2 - (1^2+2+^2+3^2) = 22

For N=10 , (1+2+...+10)^2 - (1^2+2^2+...10^2) = 2640 

Solution 

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

int main(){
    int t; 
    scanf("%d",&t);
    for(int a0 = 0; a0 < t; a0++){
        long long n; 
        scanf("%lld",&n);
        long long f1,f2,diff;
        f1=(n*(n+1))/2;
        f1=f1*f1;
        f2=(n*(n+1)*(2*n+1))/ 6;
        diff=(f1-f2);
        if (diff<0)
        diff=diff*-1;
        printf("%lld\n",diff);
    }
    return 0;
}


You can also run it on an online IDE:

https://ide.geeksforgeeks.org/6601fb42-0c0f-4c75-8058-27c871f50f58

Your feedback are always welcome! If you have any doubt you can contact me or leave a comment!  Happy Coding !! Cheers!!!


Square Free Numbers - CodeVita 9 | Round 1


Square Free Numbers

In the theory of numbers, square free numbers have a special place. A square free number is one that is not divisible by a perfect square (other than 1).

Problem Description

In the theory of numbers, square free numbers have a special place. A square free number is one that is not divisible by a perfect square (other than 1). Thus 72 is divisible by 36 (a perfect square), and is not a square free number, but 70 has factors 1, 2, 5, 7, 10, 14, 35 and 70. As none of these are perfect squares (other than 1), 70 is a square free number.

For some algorithms, it is important to find out the square free numbers that divide a number. Note that 1 is not considered a square free number.

In this problem, you are asked to write a program to find the number of square free numbers that divide a given number.

Input

The only line of the input is a single integer N which is divisible by no prime number larger than 19

Output

One line containing an integer that gives the number of square free numbers (not including 1)

Constraints

N < 10^9

Complexity

Simple

Time Limit


1

Examples



Example 1


Input
20

Output
3

Explanation
N=20

If we list the numbers that divide 20, they are

1, 2, 4, 5, 10, 20

1 is not a square free number, 4 is a perfect square, and 20 is divisible by 4, a perfect square. 2 and 5, being prime, are square free, and 10 is divisible by 1,2,5 and 10, none of which are perfect squares. Hence the square free numbers that divide 20 are 2, 5, 10. Hence the result is 3.

Example 2

Input
72

Output
3

Explanation
N=72. The numbers that divide 72 are

1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72

1 is not considered square free. 4, 9 and 36 are perfect squares, and 8,12,18,24 and 72 are divisible by one of the. Hence only 2, 3 and 6 are square free. (It is easily seen that none of them are divisible by a perfect square). The result is 3

Other Test Case

Input
290990700

Output
255

Input
4491411836

Output
31

Program:

#include <stdio.h>
int isPerfectSquare(int n) 
    for (int i = 1; i * i <= n; i++) 
    { 
        if ((n % i == 0) && (n / i == i)) 
        { 
            return 1; 
        } 
    } 
    return 0; 
int main() {
int x,i,cnt=0,j=0,y,k,a[10000];
scanf("%d",&x);
for(i=1;i<=x;i++)
{
    if(x%i==0)
    {
        a[j]=i;
        j++;
    }
}
for(i=0;i<j;i++)
{
    if((isPerfectSquare(a[i])==1)&&(a[i]!=0)&&(a[i]!=1))
    {
      y=a[i];
      for(k=0;k<j;k++)
      {
        if(a[k]!=0 && a[k]%y==0)
        a[k]=0;
       }
        a[i]=0;
     }
}
for(i=0;i<j;i++)
if(a[i]!=0)
cnt++;
printf("%d",cnt-1);
return 0;
}

You can also run it on an online IDE:    

Your feedback are always welcome! If you have any doubt you can contact me or leave a comment!  Happy Coding !! Cheers!!!

Related Links:

Grooving Monkeys- Code Vita 8 | Pre-Qualifier Zonal Round

Grooving Monkeys

Problem Description

N monkeys are invited to a party where they start dancing. They dance in a circular formation, very similar to a Gujarati Garba
or a Drum Circle. The dance requires the monkeys to constantly change positions after every 1 second.
The change of position is not random & you, in the audience, observe a pattern. Monkeys are very disciplined & follow a specific
pattern while dancing.
Consider N = 6, and an array monkeys = {3,6,5,4,1,2}.
This array (1-indexed) is the dancing pattern. The value at monkeys[i], indicates the new of position of the monkey who is standing
at the ith position.
Given N & the array monkeys[ ], find the time after which all monkeys are in the initial positions for the 1st time.

Constraints

1<=t<=10 (test cases)
1<=N<=10000 (Number of monkeys)

Input Format

First line contains single integer t, denoting the number of test cases.
Each test case is as follows -
Integer N denoting the number of monkeys.
Next line contains N integer denoting the dancing pattern array, monkeys[].

Output

t lines,
Each line must contain a single integer T, where T is the minimum number of seconds after which all the monkeys are in their
initial position.

Test Case

Example 1
Input
1
6
3 6 5 4 1 2

Output
6

Explanation
Consider N = 6, and an array monkeys = {3,6,5,4,1,2}.
Suppose monkeys are a,b,c,d,e,f, & Initial position (at t = 0) -> a,b,c,d,e,f
At t = 1 -> e,f,a,d,c,b
a will move to 3rd position, b will move to 6th position, c will move to 5th position, d will move to 4th position, e will move to
1st position and f will move to 2nd position. Thus from a,b,c,d,e,f at t =0, we get e,f,a,d,c,b at t =1. Recursively applying same
transpositions, we get following positions for different values of t.
At t = 2 -> c,b,e,d,a,f
At t = 3 -> a,f,c,d,e,b
At t = 4 -> e,b,a,d,c,f
At t = 5 -> c,f,e,d,a,b
At t = 6 -> a,b,c,d,e,f
Since at t = 6, we got the original position, therefore the answer is 6.

Program:

#include <stdio.h>

int isequal(int x[],int m)
{
    int c1=0;
    for(int k=1;k<=m;k++)
    {
        if(x[k]==k)
        c1++;
    }
    return c1;
}
int main() {
int n,a[100],i,b[100],k,c[100],cnt,t;
scanf("%d",&t);
for(k=0;k<t;k++)
{
cnt=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[i]=i;
}
z: for(i=1;i<=n;i++)
    c[a[i]]=b[i];
cnt++;
if(isequal(c,n)==n)
printf("%d\n",cnt);
else
{
    for(i=1;i<=n;i++)
    b[i]=c[i];
    goto z;
}
}
return 0;

}


You can also run it on an online IDE: https://ide.geeksforgeeks.org/IEgUyvHl1N

Your feedback are always welcome! If you have any doubt you can contact me or leave a comment!! Cheers!!!

Related Links:
Philaland Coin : https://codepiggy.blogspot.com/2020/03/philaland-coin-code-vita-8-pre.html


Philaland Coin - Code Vita 8 | Pre-Qualifier Zonal Round

Philaland Coin


Problem Description

The problem solvers have found a new Island for coding and named it as Philaland.
These smart people were given a task to make purchase of items at the Island easier by distributing various coins with different
value.
Manish has come up with a solution that if we make coins category starting from $1 till the maximum price of item present on
Island, then we can purchase any item easily. He added following example to prove his point.
Lets suppose the maximum price of an item is 5$ then we can make coins of {$1, $2, $3, $4, $5} to purchase any item ranging
from $1 till $5.
Now Manisha, being a keen observer suggested that we could actually minimize the number of coins required and gave following
distribution {$1, $2, $3}. According to him any item can be purchased one time ranging from $1 to $5. Everyone was impressed
with both of them.
Your task is to help Manisha come up with minimum number of denominations for any arbitrary max price in Philaland.

Constraints

1<=T<=100
1<=N<=5000

Input Format

First line contains an integer T denoting the number of test cases.
Next T lines contains an integer N denoting the maximum price of the item present on Philaland.

Output

For each test case print a single line denoting the minimum number of denominations of coins required.

Test Case

Example 1

Input
2
10
5

Output
4
3

Explanation
For test case 1, N=10.
According to Manish {$1, $2, $3,... $10} must be distributed.
But as per Manisha only {$1, $2, $3, $4} coins are enough to purchase any item ranging from $1 to $10. Hence minimum is 4.
Likewise denominations could also be {$1, $2, $3, $5}. Hence answer is still 4.
For test case 2, N=5.
According to Manish {$1, $2, $3, $4, $5} must be distributed.
But as per Manisha only {$1, $2, $3} coins are enough to purchase any item ranging from $1 to $5. Hence minimum is 3. Likewise
denominations could also be {$1, $2, $4}. Hence answer is still 3.

Program:

#include <stdio.h>
int sum(int x[],int l)
{
  int j,s1=0;
  for(j=1;j<=l;j++)
    s1=s1+x[j];
   return s1;
}
int main() {
int n,a[100],k=1,i,c,t,j;
scanf("%d",&t);
for(j=0;j<t;j++)
{
scanf("%d",&n);
a[1]=1;
c=0;
for(i=1;i<=n;i++)
{
    if(i>sum(a,k))
    {
        k++;
        a[i]=k;
    }
}
for(i=1;i<=k;i++)
{
    if(a[i]!=0)
    c++;
}
printf("%d\n",c);
for(i=1;i<=k;i++)
a[i]=0;
k=1;
}
return 0;
}

You can also run it on an online IDE: https://ide.geeksforgeeks.org/CqdZa41BMI

Your feedback are always welcome! If you have any doubt you can contact me or leave a comment!! Cheers!!!


Min Combinations - Code Vita 8 | Pre-Qualifier Zonal Round

Min Combinations

Problem Description

Alexander The great, while roaming the stretch of Turkey, came across a wise man.
He asked the wise man, "Who is the greatest conqueror of all?". The wise man replied, "A person with great strength and
intelligence. Whosoever can solve my puzzle will go on to become the greatest!". The puzzle is as follows; Given two integers
'n1' and 'n2', select two integers 'a' and 'b', such as to solve the equation (n1 * a + n2 * b = x). But there is a catch, 'x' is the smallest
positive integer which satisfies the equation. Can you help Alexander become the greatest?

Constraints

1 <= T <= 1000
-10^7 <= a, b <= 10^7
0 <= n1, n2 <= 10^7

Input Format

The first line contains the number of Test cases T.
Next T lines contains two space-separated integers, n1 and n2.

Output

Print the value of x.

Test Case

Example 1

Input
1
34818 45632

Output
2

Explanation
Given n1 = 34818 and n2 = 45632, if we choose a = 3553 and b = -2711, we get
=> n1 * a + n2 * b = x
=> 34818 * 3553 + 45632 * (-2711)
=> 2
Note: No other value of a and b, within the range, will give smaller value than 2.

Program

#include <stdio.h> 
int gcd(int a, int b) 
if (b == 0) 
return a; 
return gcd(b, a % b); 

int main() 
int a,b,t,i;
scanf("%d",&t);
for(i=0;i<t;i++)
{
scanf("%d %d",&a,&b);
printf("%d\n", gcd(a, b)); 
}
return 0; 

You can also run it on an online IDE: https://ide.geeksforgeeks.org/OshEmrNKoJ

Your feedback are always welcome! If you have any doubt you can contact me or leave a comment!! Cheers!!!

Related Links:

Prime Counters - Code Vita 2017 | Round 1

Prime Counters


Problem : 

Given a number N, let CP(N) denote the number of primes between 1 and N (inclusive of N). We call N a prime counter if CP(N) is a prime (N need not be a prime).  For example, CP(3) = 2, CP(4) = 2, CP(5) = 2, CP(7) = 4.

Input Format:  

An integer T, number of test cases  T lines each containing two positive integers L, R separated by space

Output Format:  

T lines containing the number of prime counters between L and R (both inclusive) in the ith test case (or NONE is no prime counter exists in that range)

Constraints:  

L ≤ R ≤ 106

Example 1 

 Input  1
  1 10

Output 
 4

Explanation 
CP(1) = 0, CP(2) = 1, CP(3) = 2, CP(4) = 2, CP(5) = 3, CP(6) = 3, CP(7) = 4= CP(8) = CP(9) = CP(10)   Hence there are 4 prime counters, 3, 4, 5, 6 in the range 1 to 10.

Example 2  

Input  2
 2 20  3 30 

Output  
  8
 8

Explanation  
Upto 10, we have 4 prime counters. Between 11 and 20 the prime counters are 11, 12, 17, 18 and hence the count is 8. Between 21 and 30, we have no prime counters.

Program:

#include <stdio.h>
int prime(int n)
{
    int k,j,p=0;
    for(k=2;k<=n;k++)
    {
        int c=0;
        for(j=1;j<=k;j++)
            if(k%j==0)
            c++;
       if(c==2)
        p++;
    }
    return p;
}
int main() 
{
int l,t,r,i,cp[1000],k,f,c=0,j,count;
scanf("%d",&t);
for(int z=1;z<=t;z++)
{
count=0;
scanf("%d %d",&l,&r);
for( i=l;i<=r;i++)
   cp[i]=prime(i);
for(j=l;j<=r;j++)
{
    c=0;
    for (k = 1;k<=cp[j]*cp[j];k++) 
    {
          if (cp[j] % k == 0) 
            c++;
        }
        if (c == 2) 
        count++;
}
printf("%d\n",count);
}
return 0;

}

You can also run it on an online IDE: https://ide.geeksforgeeks.org/YphGa2McDy

Your feedback are always welcome! If you have any doubt you can contact me or leave a comment!! Cheers!!!

Related Links:
Air in the balloonhttps://codepiggy.blogspot.com/2020/03/air-in-balloons.html

Jumble With Numbers

Jumble With Numbers

Problem

In NASA, two researchers, Mathew and John, started their work on a new planet, but while practicing research they faced a mathematical difficulty. In order to save the time they divided their work.
So scientist Mathew worked on a piece and invented a number computed with the following formula:
A Mathew number is computed as follows using the formula:
H(n) = n(2n-1)
And scientist John invented another number which is built by the following formula which is called John number.
T(n) = n(n+1)/2
Now Mathew and John are jumbled while combining their work. Now help them combine their research work by finding out number in a given range that satisfies both properties. Using the above formula, the first few Mathew-John numbers are:
1 6 15 28 …

Input Format:

Input consists of 3 integers T1,T2,M separated by space . T1 and T2 are upper and lower limits of the range. The range is inclusive of both T1 and T2. Find Mth number in range [T1,T2] which is actually a Mathew-John number.

Line 1
T1 T2 M,where T1 is upper limit of the range, T2 is lower limit of the range and M ,where Mth element of the series is required

Constraints:

0 < T1 < T2 < 1000000

Output Format:

Print Mth number from formed sequence between T1 and T2(inclusive).

Line 1
For Valid Input,print

Print Mth number from formed sequence between T1 and T2
Or
No number is present at this index

For Invalid Input,print

Invalid Input


Sample Input and Output:


SNo.InputOutput
1               
90 150 2             
120
2
20 80 6
No number is present at this index
3
-5 3 a
Invalid Input

Program:

#include <stdio.h>
int main() {
int t1,t2,m,i,j,c=0,a,b,th[100],k=0;
scanf("%d %d %d",&t1,&t2,&m);
if(t1>0&&t2>0&&m>0)
{
for(i=1;i<=t2/2;i++)
{
    a=i*((2*i)-1);
    for(j=1;j<=t2/2;j++)
    {
        b=j*(j+1)/2;
        if((a==b)&&(a>=t1&&a<=t2))
        th[k++]=a;
    }
}
   if(k<m)
    printf("No number is present at this index");
    else
    printf("%d",th[m-1]);
}
         else
         printf("Invalid Input");
return 0;
}

Output:

90 150 2

120

You can also run this in online IDE: https://ide.geeksforgeeks.org/ZndEODl1gU

Your comments and feedbacks are welcomed! If you have any doubts you can leave it on the comment! Cheers!!

Related Links: Test vita

Super Market Problem | TCS Code Vita 2023 - Zone 1 | Super Market TCS Code Vita 2023 Solution | Code Vita 2023 | Code Vita 2023 season 11 solution

 Problem Description: In a Super market we will find many variations of the same product. In the same way we can find many types of rice bag...