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

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

Codu And Sum Love 2018

Codu And Sum Love

Problem Description

```

Scanner sc = new Scanner(System.in);

long sum = 0;

int N = sc.nextInt();

for (int i = 0; i < N; i++) {

final long x = sc.nextLong(); // read input

String str = Long.toString((long) Math.pow(1 << 1, x));

str = str.length() > 2 ? str.substring(str.length() - 2) : str;

sum += Integer.parseInt(str);

}

System.out.println(sum%100);

```

Given N number of x’'s, perform logic equivalent of the above Java code and print the output

Constraints

 1<=N<=10^7 0<=x<=10^18

Input Format

 First line contains an integer N

Second line will contain N numbers delimited by space

Output

 Number that is the output of the given code by taking inputs as specified above

Explanation

Example 1

Input

 4 8 6 7 4

 Output

 64

Example 2

Input

3

1 2 3

Output

14

Program

#include <stdio.h>
long power(long k)
{
    long i,j=1;
    for(i=1;i<=k;i++)
        j=j*2;
        return j;
}
long length(long k)
{
    long ct=0,n1;
    while(k)
    {
        ct++;
        k=k/10;
    }
    return ct;
}
long reduce(long p1,long r1)
{
    long ct=0,k,cnt,rev=0,a[1000],h=0,i,sum1=0;
    while(p1)
    {
      k=p1%10;
      a[h]=k;
      h++;
      p1=p1/10;
     }
      for(i=1;i>=0;i--)
      sum1=sum1*10+a[i];
    return sum1;
}
int main() {
 long x,n,sum=0,r[70],p,c,f=0,i;
 scanf("%ld",&n);
 for(i=0;i<n;i++)
 {
    scanf("%ld",&x);
    p=power(x);
    c=length(p);
    if(c>2)
    {
    r[f++]=reduce(p,c);
    }
    else
    r[f++]=p;
 }
 for(i=0;i<n;i++)
 
 sum=sum+r[i];
   printf("%ld",(sum%100));
 
 
 return 0;
}

Output:

4 8 6 7 4

64

You can also try running it on online IDE: https://ide.geeksforgeeks.org/G3gXokhTbW

Your doubts and feedback are welcomed! you can comment it below Cheers!

Related Link: Super Ascii

Bride Hunting -Code Vita 2018 | round 1 | TCS Code Vita Solution 2018 | Bride Hunting TCS Code Vita solution

Bride Hunting

Problem Description

Sam is an eligible bachelor. He decides to settle down in life and start a family. He goes bride hunting.

He wants to marry a girl who has at least one of the 8 qualities mentioned below:-

1) The girl should be rich.

2) The girl should be an Engineer/Doctor.

3) The girl should be beautiful.

4) The girl should be of height 5.3".

5) The girl should be working in an MNC.

6) The girl should be an extrovert.

7) The girl should not have spectacles.

8) The girl should be kind and honest.

He is in search of a bride who has some or all of the 8 qualities mentioned above. On bride hunting, he may find more than one contenders to be his wife.

In that case, he wants to choose a girl whose house is closest to his house. Find a bride for Sam who has maximum qualities. If in case, there are more than one contenders who are at equal distance from Sam’'s house; then

print "“Polygamy not allowed”".

In case there is no suitable girl who fits the criteria then print “"No suitable girl found"”

Given a Matrix N*M, Sam's house is at (1, 1). It is denoted by 1. In the same matrix, the location of a marriageable Girl is also denoted by 1. Hence 1 at location (1, 1) should not be considered as the location of a marriageable Girl’s location.

The qualities of that girl, as per Sam’'s criteria, have to be decoded from the number of non-zero neighbors (max 8-way) she has. Similar to the condition above, 1 at location (1, 1) should not be considered as the quality of a Girl. See Example section to get a better understanding.

Find Sam, a suitable Bride and print the row and column of the bride, and find out the number of qualities that the Bride possesses.

NOTE: - Distance is calculated in number of hops in any direction i.e. (Left, Right, Up, Down and Diagonal)

Constraints

2 <= N,M <= 10^2

Input Format

First Line contains the row (N) and column (M) of the houses.

Next N lines contain the data about girls and their qualities.

Output

It will contain the row and column of the bride, and the number of qualities that Bride possess separated by a colon (i.e. :).

Explanation

Example 1

Input:

2 9

1 0 1 1 0 1 1 1 1

0 0 0 1 0 1 0 0 1

Output:

1:7:3

Explanation:

The girl and qualities are present at (1,3),(1,4),(1,6),(1,7),(1,8),(1,9),(2,4),(2,6),(2,9).

The girl present at (1,3) has 2 qualities (i.e. (1,4)and (2,4)).

The girl present at (1,4) has 2 qualities.

The Bride present at (1,6) has 2 qualities.

The Bride present at (1,7) has 3 qualities.

The Bride present at (1,8) has 3 qualities.

The Bride present at (1,9) has 2 qualities.

The Bride present at (2,4) has 2 qualities.

The Bride present at (2,6) has 2 qualities.

The Bride present at (2,9) has 2 qualities.

As we see, there are two contenders who have maximum qualities, one is at (1,7) and another at (1,8).

The girl who is closest to Sam's house is at (1,7). Hence, she is the bride.

Hence, the output will be 1:7:3.

Example 2

Input:

6 6

1 0 0 0 0 0

0 0 0 0 0 0

0 0 1 1 1 0

0 0 1 1 1 0

0 0 1 1 1 0

0 0 0 0 0 0

Output:

4:4:8

Explanation:

The bride and qualities are present at (3,3),(3,4),(3,5),(4,3),(4,4),(4,5),(5,3),(5,4),(5,5)

The Bride present at (3,3) has 3 qualities (i.e. (3,4),(4,3) and (4,4)).

The Bride present at (3,4) has 5 qualities.

The Bride present at (3,5) has 3 qualities.

The Bride present at (4,3) has 5 qualities.

The Bride present at (4,4) has 8 qualities.

The Bride present at (4,5) has 5 qualities.

The Bride present at (5,3) has 3 qualities.

The Bride present at (5,4) has 5 qualities.

The Bride present at (5,5) has 3 qualities.

As we see, the girl present in (4,4) has maximum number of Qualities. Hence, she is the bride.

Hence, the output will be 4:4:8.

Solution in C:

 
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
// Function to check if given indices are valid in the matrix
int isValid(int row, int col, int N, int M) {
return (row >= 0 && row < N && col >= 0 && col < M);
}
// Function to count the number of qualities a girl possesses
int countQualities(int matrix[][100], int row, int col, int N, int M) {
int count = 0;
for (int i = row - 1; i <= row + 1; i++) {
for (int j = col - 1; j <= col + 1; j++) {
if (isValid(i, j, N, M) && !(i == row && j == col) && matrix[i][j] == 1) {
count++;
}
}
}
return count;
}
// Function to find the suitable bride for Sam
void findBride(int matrix[][100], int N, int M) {
int minDistance = N + M; // Initialize to maximum possible distance
int maxQualities = 0;
int brideRow = -1, brideCol = -1;
// Loop through the matrix to find the bride with maximum qualities
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (matrix[i][j] == 1) {
int qualities = countQualities(matrix, i, j, N, M);
if (qualities > maxQualities) {
maxQualities = qualities;
brideRow = i;
brideCol = j;
} else if (qualities == maxQualities) {
// If multiple brides have the same number of qualities,
// find the one with minimum distance to Sam's house
int distance = abs(0 - i) + abs(0 - j);
if (distance < minDistance) {
minDistance = distance;
brideRow = i;
brideCol = j;
} else if (distance == minDistance) {
printf("Polygamy not allowed\n");
return;
}
}
}
}
}
// If no suitable bride found
if (brideRow == -1 || brideCol == -1) {
printf("No suitable girl found\n");
} else {
printf("%d:%d:%d\n", brideRow + 1, brideCol + 1, maxQualities);
}
}
int main() {
int N, M;
scanf("%d %d", &N, &M);
int matrix[100][100];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
scanf("%d", &matrix[i][j]);
}
}
findBride(matrix, N, M);
return 0;
}
 

Alternate Solution (Brute Force):

#include<stdio.h>
int main()
{
int n,m,i,g[50][50],j,p,q,max=0,cnt=0,k=1,c=0,u=1,x[30],y[30],t1,min=0, sc[50],e,f,ct=0,a[50],count=0,t2=0,t=0;
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
scanf("%d",&g[i][j]);
} }
g[1][1]=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{ cnt=0;
if(g[i][j]==1)
{
t++;
for(p=i-1;p<=i+1;p++)
{
for(q=j-1;q<=j+1;q++)
{
if(g[p][q]==1)
{ cnt++;
} } }
cnt=cnt-1;
a[k]=cnt;
k++;
} } }
for(k=1;k<=t;k++)
{ if(a[k]>max) max=a[k];
}
if(max==0)
{ printf("No suitable girl found"); goto x; }
for(k=1;k<=t;k++)
{ if(a[k]==max)
c++; }
for(k=1;k<=t;k++)
{ t2=0;
if(a[k]==max)
{ for(i=1;i<=n;i++)
{ for(j=1;j<=m;j++)
{ if(g[i][j]==1) t2++;
if(t2==k)
{ x[u]=i; y[u]=j; u++;
} } } } }
t1=u-1;
if(c==1)
printf("%d:%d:%d",x[1],y[1],max);
else
{ for(u=1;u<=t1;u++)
{ e=x[u]-1;
f=y[u]-1;
if(e>=f)
{ sc[u]=e;
}
else sc[u]=f;
}
min=sc[1];
for(u=1;u<=t1;u++)
{ if(sc[u]<min) min=sc[u];
}
for(u=1;u<=t1;u++)
{ if(sc[u]==min) count++;
}
if(count>1)
printf("Polygamy not allowed");
if(count==1)
{ for(u=1;u<=t1;u++)
{ if(sc[u]==min)
printf("%d:%d:%d",x[u],y[u],max);
} } }
x: return 0;
}

OUTPUT:

6 6
1 0 0 0 0 0
0 0 0 0 0 0
0 0 1 1 1 0
0 0 1 1 1 0
0 0 1 1 1 0
0 0 0 0 0 0

4:4:8

Hey guys you can run this program in the online ide in this link: 

https://ide.geeksforgeeks.org/online-c-compiler/e9bd0a6a-12a8-459f-82dc-ebc592e1d16e

Your feedback are welcomed and can comment or post your doubts in the comment Cheers!

Related Links: 

https://codepiggy.blogspot.com/2024/03/super-market-problem-tcs-code-vita-2023.html

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