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:    

https://ide.geeksforgeeks.org/tttw8dQwDN

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: https://codepiggy.blogspot.com/2020/03/grooving-monkeys-code-vita-8-pre.html

Bank Compare | Code Vita 2018 | round 1

Bank Compare

 Problem Description

There are two banks; Bank A and Bank B. Their interest rates vary. You have received offers from both bank in terms of annual rate of interest, tenure and variations of rate of interest over the entire tenure.

You have to choose the offer which costs you least interest and reject the other.

Do the computation and make a wise choice.

The loan repayment happens at a monthly frequency and Equated Monthly Installment (EMI) is calculated using the formula given below :

EMI = loanAmount * monthlyInterestRate /

( 1 - 1 / (1 + monthlyInterestRate)^(numberOfYears * 12))

Constraints

1 <= P <= 1000000

1 <=T <= 50

1<= N1 <= 30

1<= N2 <= 30

Input Format

First line : P – principal (Loan Amount)

Second line : T – Total Tenure (in years).

Third Line : N1 is number of slabs of interest rates for a given period by Bank A. First slab starts from first year and second slab starts from end of first slab and so on.

Next N1 line will contain the interest rate and their period.

After N1 lines we will receive N2 viz. the number of slabs offered by second bank.

Next N2 lines are number of slabs of interest rates for a given period by Bank B. First slab starts from first year and second slab starts from end of first slab and so on.

The period and rate will be delimited by single white space.

Output

Your decision – either Bank A or Bank B.

Explanation

Example 1

Input

10000

20

3

5 9.5

10 9.6

5 8.5

3

10 6.9

5 8.5

5 7.9

Output

Bank B

Example 2

Input

500000

26

3

13 9.5

3 6.9

10 5.6

3

14 8.5

6 7.4

6 9.6

Output

Bank A

Program:

#include <stdio.h>

double power(double b,int a)

{

    int i;

    double pow=1;

    for(i=0;i<a;i++)

    {

        pow=pow*b;

    }

    return pow;

}

int main() {

double p,s,mi,sum,emi,j1,j,bank[5],sq;

int y,n,k,i,yrs,y1,l=0;

    scanf("%lf",&p);

scanf("%d",&y);

for(k=0;k<2;k++)

{

scanf("%d",&n);

sum=0;

for(i=0;i<n;i++)

{

    scanf("%d",&yrs);

    scanf("%lf",&s);

    mi=0;

    j=s/1200;

    j1=1+j;

    y1=yrs*12;

    sq=power(j1,y1);

    emi=p*(j/(1-(1/(sq))));

    mi=emi*y1;

    sum=sum+mi;

}

bank[l++]=sum;

}

if(bank[0]<bank[1])

printf("Bank A");

else

printf("Bank B");

return 0;

}

Output:

10000

20

3

5 9.5

10 9.6

5 8.5

3

10 6.9

5 8.5

5 7.9

Bank B

  

You can also run it in an online IDE: https://ide.geeksforgeeks.org/sPEYMvF71Y

If you have any doubts you can leave it in the comment section or contact me!!
Your feedback are welcomed so kindly leave your feedback below! Cheers!

Related Links: Stone Game- One Four

TestVita | Code Vita 2015 | round 2

TestVita

Problem:

TCS is working on a new project called "TestVita". There are N modules in the project. Each module (i) has completion time denoted in number of hours (Hi) and may depend on other modules. If Module x depends on Module y then one needs to complete y before x.

As Project manager, you are asked to deliver the project as early as possible.
Provide an estimation of amount of time required to complete the project.

Input Format:

First line contains T, number of test cases.

For each test case: 

1. First line contains N, number of modules.
2. Next N lines, each contain:
   • (i) Module ID
   • (Hi) Number of hours it takes to complete the module
   • (D) Set of module ids that i depends on - integers delimited by space.

Output Format:

Output the minimum number of hours required to deliver the project.

Constraints:

1. 1 <= T <= 10

2. 0 < N < 1000; number of modules

3. 0 < i <= N; module ID 

4. 0 < Hi < 60; number of hours it takes to complete the module i

5. 0 <= |D| < N; number of dependencies

6. 0 < Dk <= N; module ID of dependencies

Sample Input and Output

SNo.	Input	Output
1	1 5 1 5 0 2 6 1 3 3 2 4 2 3 5 1 3	16

Program:

#include <stdio.h>

int main() {

int n,m[10],t[10],d[10],q,a,i,sum=0;

scanf("%d",&a);

for(q=1;q<=a;q++)

{

scanf("%d",&n);

for(i=0;i<n;i++)

    scanf("%d %d %d",&m[i],&t[i],&d[i]);

    for(i=0;i<n-1;i++)

    {

            if(d[i]==d[i+1])

            {

                if(t[i]<t[i+1])

                t[i]=0;

                else

                t[i+1]=0;

            }

    }

   for(i=0;i<n;i++)

   {

       sum=sum+t[i];

   }

    printf("%d",sum);

}

return 0;

}

Output:

1
5
1 5 0
2 6 1
3 3 2
4 2 3
5 1 3

16

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

Your feedback are welcomed! If you have any doubts you can contact me or comment below! Cheers!

 Related Link: Bank Compare

Reverse Gear | Code Vita 2015 | round 1

Reverse Gear

Problem Description:

        A futuristic company is building an autonomous car. The scientists at the company are training the car to perform Reverse parking. To park, the car needs to be able to move in backward as well as forward direction. The car is programmed to move backwards B meters and forwards again, say F meters, in a straight line. The car does this repeatedly until it is able to park or collides with other objects. The car covers 1 meter in T units of time. There is a wall after distance D from car's initial position in the backward direction.

The car is currently not without defects and hence often hits the wall. The scientists are devising a strategy to prevent this from happening. Your task is to help the scientists by providing them with exact information on amount of time available before the car hits the wall.

Input Format:

First line contains total number of test cases, denoted by N
Next N lines, contain a tuple containing 4 values delimited by space
F B T D, where

1. F denotes forward displacement in meters
2. B denotes backward displacement in meters
3. T denotes time taken to cover 1 meter
4. D denotes distance from Car's starting position and the wall in backward direction

Output Format:

For each test case print time taken by the Car to hit the wall

Constraints:

First move will always be in backward direction

1 <= N <= 100

backward displacement > forward displacement i.e. (B > F)

forward displacement (F) > 0

backward displacement (B) > 0

time (T) > 0 

distance (D) > 0

All input values must be positive integers only

Sample Input and Output

SNo.	Input	Output
1	2 6 9 3 18 3 7 5 20	162 220

Program:

#include <stdio.h>
int main() {
int f,b,d,t,sdist,sdisp,step,rd,td,tot,tt,test;
scanf("%d",&test);
while(test)
{
scanf("%d %d %d %d",&f,&b,&t,&d);
sdist=b+f;
sdisp=b-f;
step=(d-b)/sdisp;
if((d-b)%sdisp!=0)
step=step+1;
rd=d-(step*sdisp);
tot=(step*sdist)+rd;
tt=tot*t;
printf("%d\n",tt);
test--;
}
return 0;
}

Output:

2
6 9 3 18
3 7 5 20

162
220

You can also run it on an online IDE: https://ide.geeksforgeeks.org/S994F0QfMs
Your feedback and if you have any doubts it is welcomed! Do contact me or comment it below! Cheers!

Related Links: consecutive prime sum