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

Consecutive Prime Sum | Code Vita 2016 | round 1

Problem Description:

Some prime numbers can be expressed as Sum of other consecutive prime numbers.
For example

5 = 2 + 3
17 = 2 + 3 + 5 + 7
41 = 2 + 3 + 5 + 7 + 11 + 13

Your task is to find out how many prime numbers which satisfy this property are present in the range 3 to N subject to a constraint that summation should always start with number 2.
Write code to find out number of prime numbers that satisfy the above mentioned property in a given range.
Input Format:

First line contains a number N

Output Format:
Print the total number of all such prime numbers which are less than or equal to N.

Sample Input and Output

SNo.	Input	Output	Comment
1	20	2	(Below 20, there are 2 such numbers: 5 and 17). 5=2+3 17=2+3+5+7
2	15	1

Program:

#include <stdio.h>
int prime(int b)
{
    int j,cnt;
   cnt=1;
     for(j=2;j<=b/2;j++)
     {
         if(b%j==0)
         cnt=0;
     }
     if(cnt==0)
     return 1;
     else
     return 0;
}
int main() {
 int i,j,n,cnt,a[25],c,sum=0,count=0,k=0;
 scanf("%d",&n);
 for(i=2;i<=n;i++)
 {
     cnt=1;
     for(j=2;j<=n/2;j++)
     {
         if(i%j==0)
         cnt=0;
     }
     if(cnt==1)
     {
        a[k]=i;
        k++;
        }
 }
 for(i=0;i<k;i++)
 {
     sum=sum+a[i];
    c= prime(sum);
    if(c==1)
    count++;
 }
 printf("%d",count);
 return 0;
}

Output:

20

2

You can also run it on a online IDE: https://ide.geeksforgeeks.org/XcOKzTd4Ik

If you have any doubt you can contact me or comment it below! Your comments and feedbacks are also welcomed!! Cheers!!

Related Links: Jumble with Numbers

Date Time | Code Vita 2018 | round 1

Date Time

Problem Description

Arun and his sister Usha are challenging each other with some mathematical puzzles. Usha, the cleverer one, has come up with the idea of givingArun 12 distinct digits from 0 to 9, and have him form the largest date time in 2018 with them. Arun is a little nervous, and asks you to help him with a computer program.

Usha will give Arun 12 distinct digits. He needs to create a date time combination in the year 2018: the date in the MM/DD form (all four digits must be present), and the time in the format HH:MM (all four digits must be present). The date may be from 01/01 to 12/31 and the time may be from 00:00 to 23:59 (in the 24 hour format). The digits provided may be used only once in the answer that Arun gives.

If more than one date time combination may be formed, Arun needs to give the latest valid date time possible in the year 2018.

Constraints

Single digits (any of 0-9)

Input Format

A line consisting of a sequence of 12 (not necessarily distinct) single digits (any of 0-9) separated by commas. The sequence will be non-decreasing.

Output

The maximum possible valid date time in the year 2018. The output must be in the format

MM/DD HH:MM

If no date time can be constructed, the output should be 0

Explanation

Example1 :

Input

0,0,1,2,2,2,3,5,9,9,9,9

Output

12/30 22:59

Explanation

The 12 digits to be used by Arun are given.

The maximum valid date time using only the digits given, and with each digit used at most once is

12/30 22:59

This is the output.

Example 2

Input

3,3,3,3,3,3,3,3,3,3,3,3

Output

0

Explanation

As no digit less than 3 is present in the input, a valid month cannot be formed. Hence no valid Date time can be formed with the input digits.

Program

#include<stdio.h>
int isLeapYear(int y)
{
    if(y % 4 == 0)
    {
        if(y % 100 == 0)
        {
            if(y % 400 == 0)
            {
                return 1;
            }
            else
            {
                return 0;
            }
        }
        else
        {
            return 1;
        }
    }
    
    return 0;
}

int is_valid_date_time(int date_time_arr[], int n)
{
    int month;
    if(n >= 2)
    {
        month = date_time_arr[0] * 10 + date_time_arr[1];
        if(!(month >= 1 && month <= 12))
        {
            return 0;
        }
    }
    
    if(n >= 4)
    {
        int days_in_each_month[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        days_in_each_month[1] += isLeapYear(2018);
        
        int day = date_time_arr[2] * 10 + date_time_arr[3];
        if(!(day >= 1 && day <= days_in_each_month[month - 1]))
        {
            return 0;
        }
    }
    
    if(n >= 6)
    {
        int hour = date_time_arr[4] * 10 + date_time_arr[5];
        if(!(hour >= 0 && hour <= 23))
        {
            return 0;
        }
    }
    
    if(n >= 8)
    {
        int min = date_time_arr[6] * 10 + date_time_arr[7];
        if(!(min >= 0 && min <= 59))
        {
            return 0;
        }
    }
    
    return 1;
}

int isFound = 0;
int max_time_in_2018[8] = {0};

int is_max(int inp_arr[])
{
    for(int i = 0; i < 8; i ++)
    {
        if(max_time_in_2018[i] == inp_arr[i])
        {
            continue;
        }
        else if(max_time_in_2018[i] >inp_arr[i])
        {
            return 0;
        }
        else 
        {
            return 1;
        }
    }
    
    return 0;
}

void time_computing(int inp_arr[], 
                    int date_time_arr[], int sel_cnt,
                    int used[])
{
    if(!is_valid_date_time(date_time_arr, sel_cnt)) 
    {
        return;
    }
    
    if(sel_cnt == 8)
    {
        if(is_valid_date_time(date_time_arr, sel_cnt))
        {
            isFound = 1;
            if(is_max(date_time_arr))
            {
                for(int i = 0; i < 8; i++)
                {
                    max_time_in_2018[i] = date_time_arr[i];
                }
            }
        }
        
        return;
    }
    
    // Select current item
    for(int i = 0; i< 12; i++)
    {
        if(used[i] == 1)
        {
            continue;
        }
        
        date_time_arr[sel_cnt] = inp_arr[i];
        used[i] = 1;
        time_computing(inp_arr,date_time_arr, sel_cnt + 1, used);
        used[i] = 0;
    }              
}

int main()
{
    int inp_arr[12], date_time_arr[8];
    scanf("%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d,%d",
          &inp_arr[0],&inp_arr[1],&inp_arr[2],&inp_arr[3],
          &inp_arr[4],&inp_arr[5],&inp_arr[6],&inp_arr[7],
          &inp_arr[8],&inp_arr[9],&inp_arr[10],&inp_arr[11]);

    int used[12] = {0};
    
    time_computing(inp_arr, date_time_arr, 0, used);
    if(isFound == 1)
    {
        printf("%d%d/%d%d %d%d:%d%d",
         max_time_in_2018[0],max_time_in_2018[1],max_time_in_2018[2],max_time_in_2018[3],
         max_time_in_2018[4],max_time_in_2018[5],max_time_in_2018[6],max_time_in_2018[7]);
    }
    else
    {
        printf("0");
    }
    
    return 0;

}

Output

0,0,1,2,2,2,3,5,9,9,9,9

12/30 22:59

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

Your comments and feedback are welcomed!! If you have any doubts do contact me! Cheers!

Related Links: Parallelograms 2018

Super Ascii - Code Vita 2014 | round 2

Super Ascii

Problem Decription:

In the Byteland country a string "S" is said to super ascii string if and only if count of each character in the string is equal to its ascii value.

In the Byteland country ascii code of 'a' is 1, 'b' is 2 ...'z' is 26.

Your task is to find out whether the given string is a super ascii string or not.

Input Format:

First line contains number of test cases T, followed by T lines, each containing a string "S".

Output Format:

For each test case print "Yes" if the String "S" is super ascii, else print "No"

Constraints:

1<=T<=100

1<=|S|<=400, S will contains only lower case alphabets ('a'-'z').

Sample Input and Output

SNo.	Input	Output
1	2 bba scca	Yes No

Explanation:

In case 1, viz. String "bba" -
The count of character 'b' is 2. Ascii value of 'b' is also 2.
The count of character 'a' is 1. Ascii value of 'a' is also 1.
Hence string "bba" is super ascii.

Program:

#include <stdio.h>
int main() {
    char s[30];
    int i,num[30]={0},isascii,n;
    scanf("%d",&n);
    while(n--)
    {
    scanf("%s",s);
    i=0;
    isascii=1;
    while(s[i]!='\0')
    {
        if((s[i]>='a')&&(s[i]<='z'))
        num[s[i]-'a']++;
        s[i]='\0';
        i++;
    }
    for(i=0;i<26;i++)
    {
        if((num[i]>0)&&(num[i]!=(i+1)))
        isascii=0;
        num[i]=0;
    }
    if(isascii)
    printf("yes\n");
    else
    printf("no");
    }
    return 0;
}

Output:

2

bba

scca

yes

no

You can also run it on the online IDE: https://ide.geeksforgeeks.org/q64aeIcLxM

Your feedback and comments are welcomed! If you have an doubt can contact me or comment below! Cheers!

Related Link: Date Time 2018

Zombie World

Zombie World

Zoya has developed a new game called Zombie World. The objective of the game is to kill all zombies in given amount of time. More formally,

-         N represents the total number of zombies in the current level

-         T represents the maximum time allowed for the current level

-         P represents the initial energy level a player starts with

-         Ei defines the energy of the i-th zombie

-         D defines the minimum energy the player needs, to advance to the next level

When a player energy is greater than or equal to the i-th zombie's energy, the player wins. Upon winning, the player will be awarded with an additional energy equal to the difference between current zombie energy and the player energy.

One unit of time will be taken to complete the fight with a single zombie.

Rules of the game:-

-         At any given time, a player can fight with only one zombie

-         Player is allowed to choose any one zombie to fight with.

Your task is to determine whether the player will advance to the next level or not, if he plays optimally.

Input Format:

The first line contains the number of test cases (K)

Each test case consists of three parts:

1. The total number of zombies (N) and the maximum time allowed (T)
2. Array of size N, which represents the energy of zombies (E)
3. The initial energy level a player (P) and the minimum energy required to advance (D)

Output Format:
Print "Yes" if a player can advance to the next level else print "No".

Constraints:

1<=K<=10

1<=N<=50

1<=Ei<=500

1<=T<=100

1<=D<=2000

1<=P<=500

Sample Input and Output

SNo.	Input	Output
1	1 2 3 4 5 5 7	Yes

PROGRAM:

#include<stdio.h>
int main()
{
 int n,t,e[20],i,pe,me,k;
 scanf("%d",&k);
 while(k)
 {
 scanf("%d",&n);
 scanf("%d",&t);
 for(i=0;i<n;i++)
 scanf("%d",&e[i]);
 scanf("%d",&pe);
 scanf("%d",&me);
 if(t<n)
 goto x;
 else
 {
  for(i=0;i<n;i++)
  {
   if(pe>=e[i])
   {
    pe=pe+(pe-e[i]);
   }
  }
 if(pe<=me)
 printf("yes\n");
 else
x: printf("no\n");
 }
 
    k--;
 }
 return 0;
}

OUTPUT: 

1
2 3
4 5
5 7
Yes

You can directly run it on a IDE: https://ide.geeksforgeeks.org/3un9lTbXuV

You can comment your feedback and doubts if any cheers!

Related Link:Bride Hunting

Minimum Product Array

         Minimum Product Array



TCS codevita 2016 round 1:
        The task is to find the minimum sum of Products of two arrays of the same size, given that k modifications are allowed on the first array. In each modification, one array element of the first array can either be increased or decreased by 2.Note- the product sum is Summation (A[i]*B[i]) for all i from 1 to n where n is the size of both arrays.

Input Format:
         First line of the input contains n and k delimited by white space Second line contains the Array A (modifiable array) with its values delimited by spaces Third line contains the Array B (non-modifiable array) with its values delimited by spaces.



Output Format:

Output the minimum sum of products of the two arrays.

Constraints:

1 ≤ N ≤ 10^50 ≤ |A[i]|, |B[i]| ≤ 10^50 ≤ K ≤ 10^9

Sample       Input                   Output


1.                3 5                            -31

                   1 2 -3

                  -2 3 -5



2.               5 3                              25

                  2 3 4 5 4

                  3 4 2 3 2




Explanation for sample 1:

     Here total numbers are 3 and total modifications allowed are 5. So we modified A[2], which is -3 and increased it by 10 (as 5 modifications are allowed). Now final sum will be
(1 * -2) + (2 * 3) + (7 * -5)
-2 + 6 - 35
-31

-31 is our final answer.




Explanation for sample 2:

     Here total numbers are 5 and total modifications allowed are 3. So we modified A[1], which is 3 and decreased it by 6 (as 3 modifications are allowed).
Now final sum will be
(2 * 3) + (-3 * 4) + (4 * 2) + (5 * 3) + (4 * 2)
6 - 12 + 8 + 15 + 8
25

25 is our final answer. 




PROGRAM:

#include<stdio.h>
int main()
{
 int m[10],i,min,max,k,n,p=1,sum=0,u[10],mins;
 scanf("%d",&n);
 scanf("%d",&k);
 for(i=0;i<n;i++)
 scanf("%d",&u[i]);
 for(i=0;i<n;i++)
 scanf("%d",&m[i]);
 min=m[0];
 max=m[0];
 for(i=0;i<n;i++)
 {
  if(m[i]<min)
  min=m[i];
  if(m[i]>max)
  max=m[i];
 }
 if (min<0&&max<0)
 mins=min<max?min:max;
 else if(min>0&&max>0)
 mins=max>min?max:min;
 else
 {
 if((min-max)<-(2*min))
  mins=min;
  else 
  mins=max;
 }
 for(i=0;i<n;i++)
 {
  if(mins==m[i]&&mins>0)
   {

u[i]=u[i]-(2*k);
   goto x;
   }
   if(mins==m[i]&&mins<0)
    { 
    u[i]=u[i]+(2*k);
    goto x;
    }
  }
x:for(i=0;i<n;i++)
 {
 p=u[i]*m[i];
 sum=sum+p;
 }
 printf("%d",sum);
 return 0;
 
}

OUTPUT:

5 3                              

2 3 4 5 4

3 4 2 3 2

25

You can directly run it on a IDE: https://ide.geeksforgeeks.org/lP9ISaZ9yx
You can comment your feedback and doubts if any cheers!

Related links: Zombie World