Questions & Solutions to Quiz-III
Question
Answers
-
Yes guys, i think i will wait till tomorrow and then we can start posting the solutions ): But as the questions may not be repeated, i guess we can atleast paste the questions here
so that others who are interested can try to solve it. -
Harshil_Patel_03b5f2 wrote: Write a program to pick out squarefree numbers from a given set of numbers. The criteria for a squarefree number is that it should not be a square value of its divisors and also its divisor should not be a sqaure value of its divisors. For example, 10 is square-free but 18 is not, as it is divisible by 9 = 32 .
There are two methods used in this program and they are getNoOfSquareFreeNumbers and getSquareFreeNumbers. The method getNoOfSquareFreeNumbers uses a range of integer values and returns a single integer value which is the count of square free numbers present. The second method getSquareFreeNumbers returns all the numbers that satisfy the criteria for sqare free number.
Example 1:
Input
from = 1
to = 10
Output
Function getNoOfSquareFreeNumbers return : 7
Function getSquareFreeNumbers returns : {1,2,3,5,6,7,10}
Explanation:In this example the input range of numbers is from 1 to 10. The numbers that are missing in the output are {4,8 and 9}. If we consider the integer 4 we can see that the divisor 2 when squared will result in 4. So it is not a sqarefree number. The same goes for 8 and 9.
Example 2:
Input
from = 4383
to = 4400
Output
Function getNoOfSquareFreeNumbers return : 11
Function getSquareFreeNumbers returns : {4385, 4386, 4387, 4389, 4390, 4391, 4393, 4395, 4397, 4398, 4399}
For C solutions
Header File : SquareFreeNumbers.h
Function Name : int getNoOfSquareFreeNumbers(int from, int to), int* getSquareFreeNumbers(int from, int to)
Directory Name : squarefreenumbers
File Name : SquareFreeNumbers.c
For C++ solutions
Header File : SquareFreeNumbers.h
Class Name : SquareFree
Function Name : int getNoOfSquareFreeNumbers(int from, int to), int* getSquareFreeNumbers(int from, int to)
Directory Name : squarefreenumbers
FileName : SquareFreeNumbers.cpp
#include"SquareFreeNumbers.h"
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int isPerfectSquare(int);
int isSquareFree(int);
int isSquareFree(int no) {
int j=0;
for(j=2 ; j<=no ; j++) {
if(no%j==0) { // factor
if(isPerfectSquare(j)) { //Not square free
return 0;
}
}
}
return no;
}
int getNoOfSquareFreeNumbers(int from, int to) {
int i=0,j=0, cnt=0, flag=0;
for(flag=0, i=from ; i<=to ; i++) {
if(isSquareFree(i)) {
cnt++;
}
}
return cnt;
}
int* getSquareFreeNumbers(int from, int to) {
int *arr;
int i, cnt=0;
arr = (int *)malloc(sizeof(int) * (getNoOfSquareFreeNumbers(from, to)));
for(i=from ; i<=to ; i++) {
if(isSquareFree(i)) {
arr[cnt++]=i;
}
}
return arr;
}
int isPerfectSquare(int n) {
int i=1;
while( (i*i) != n) {
if((i*i) >= n) {
return 0;
}
i++;
}
return i;
}
void dsmain() {
int n,from=4383, to=4400, i, *arr;
from=1, to=10;
n=getNoOfSquareFreeNumbers(from, to);
arr = getSquareFreeNumbers(from, to);
printf("Total No of Square Free Numbers : %d\n",n);
printf("The square free numbers are :\n");
for(i=0 ; i<n ; i++) {
printf("%d ",arr
);
}
} -
Varun_Modi_a59ed9 wrote: Now I have the answer to the 1st question which works perfectly... but the problem is in the 2nd question.. can someone help me out in the 2nd question ???
As i didnt had enough time left, i was not able to solve it,, but even now i m not able to get the logic that i should use to get the solution..
Sorry m8 my friend also got one of those question, it was a hard one, i still cant find out the logic of it
-
Alright people, finally i hv cracked the problem.. I have derived the solution, and its so easy...
Does anyone wants to have the solution??? Now the solution is simple, but try it urself first.. If you are not able to do it, i will post the answer here... I will wait for 3 people to ask for the answer here, than i will post the answer...
Harshil will also get a good response to this thread, after all it was his idea to start this thread and where we all met
-
When, you said about the multiple answers exist, I got a way to find a valid answer....
Though my code same output for the 1st example, for 2nd one it gives a different but a valid answer to the example... this can be extended to any question and it will give a valid answer if it exists...
Will surely like to know what logic you used for your code -
Ya guys, post the logic its becoming harder to wait
-
Hey buddy, I was not taunting or anything like that... Its nothing like that.. i m sorry if u felt so.. i was just highlighting the points of my code..
Can you post your code also??? -
First of all thanks varun for posting the code. I now finally have understood the logic after seeing the code, the logic seems to look like a piece of cake
why the hell we wasn't able to solve such an easy question hehe
And one more thing i have to point ut guys. Please dont fight, we need to create a good and healthy community here -
@ harshil
u r right dude.....
v should not fight here,...we are the members ..
if we won't unite then Admins will take the advantage of this
-
@Varun, i have posted the question to that maze problem that you was requesting It was also a hard one, i cant find out the solution to it. Also one more problem is there about the BUS ROUTE, i will post that later, after we have done discussions on this MAZE problem.
-
Sure m8, let me try finding the image to that maze problem. I also think that the greedy approach can be used. The problem is that it will become to complex
-
OK here is the link to the maze image.
-
Thanks sanket for the Happy Numbers problem
and varun, on the first look the problem seems simple, but when we try to implement it we get stuck. the main problem i faced was how to make the computer know in which direction to go. Now to make it easy, suppose we assume that we want to ONLY move in right down direction, but then when i tried implementing my program got stuck in a loop cause when it shifted the control to another box in the maze image, it found out that the earlier box which we came from was the minimum, and hence it tried shifting the control to there so i guess we will have to keep track of what all places we visited, and if have already visited a place, then find the next minimum. -
Sanket, Thanks for the FLAMES problem and solution
Can you help us try solving the MAZE problem ? it too seems to be complicated. -
Maze problem .............solution .............
#include <stdio.h>
#include<alloc.h>
#include <conio.h>
int r = 4;
int c = 6;
int values[][20] = { { 5, 11, 11, 11, 11, 11},
{ 1, 11, 11, 11, 10, 11},
{ 1, 1, 11, 1 , 1 , 1 },
{ 11, 1, 1 , 1 , 10 ,1}};
int min(int a,int b);
int minimum(int arr[],int visited[],int n);
int makeCostMatrix(int r,int c,int arr[20][20],int *cost[400]);
int mazeMove(int r,int c,int values[][20]);int min(int a,int b)
{
return a<b?a:b;
}int minimum(int arr[],int visited[],int n)
{
int small=9999,i;
for(i=1;i<=n;i++)
{
if(visited==1)
continue;
if(arr<small)
small=arr;
}
for(i=1;i<=n;i++)
{
if(visited==1)
continue;
if(arr==small)
return i;
}
return 0;
}int makeCostMatrix(int r,int c,int arr[20][20],int *cost[400])
{
int cnt=0,i,j;
for(i=0;i<r;i++)
{
for(j=0;j<c;j++)
{
int nodeNo = i*c+j;
if(j+1<c) //next in row
{
cost[nodeNo][nodeNo+1]=arr[nodeNo/c][(nodeNo+1)%c];
cnt++;
}
if(j-1>=0) //prev in row
{
cost[nodeNo][nodeNo-1]=arr[(nodeNo-1)/c][(nodeNo)%c];
cnt++;
}
if(i+1<r) //down in col
{
cost[nodeNo][nodeNo+c]=arr[(nodeNo+c)/c][(nodeNo)%c];
cnt++;
}
if(i-1>=0) //up in col
{
cost[nodeNo][nodeNo-c]=arr[(nodeNo)/c][(nodeNo-c)%c];
cnt++;
}
}
}
return cnt/2;
}int mazeMove(int r,int c,int values[][20])
{
int i,j,k,l[400],path[400],pl=0,visited[400]={0},v;
int start=0,end=r*c-1,cnt=r*c-1;
int *cost[400];
for(i=0;i<400;i++)
cost = (int*)malloc(400);
for(i=0;i<r*c;i++)
for(j=0;j<r*c;j++)
cost[j]=9999;
makeCostMatrix(r,c,values,cost);
for(i=0;i<400;i++)
{
l=9999;
path=-1;
}
v=start;
visited[v]=1;
path[start]=0;
for(i=0;v!=end;i++)
{
for(j=0;j<=cnt;j++)
{
if(visited[j]==1)
continue;
l[j]=min(l[j],pl+cost[v][j]);
if(min(l[j],pl+cost[v][j])==pl+cost[v][j])
path[j]=v;
}
v=minimum(l,visited,cnt);
visited[v]=1;
pl=l[v];
}
for(k=0,i=end;i!=start
{
visited[k++]=path;
i=path;
}
return pl+values[0][0];
}void main()
{
clrscr();
printf("\n%d",mazeMove(r,c,values));
getch();
} -
Thanks dude for the code. It would be nice if you give the logic of your code, its a bit tricky
-
I think no one is interested anymore in that maze solution.
Lets post another question
All replies
-
Yes guys, i think i will wait till tomorrow and then we can start posting the solutions ): But as the questions may not be repeated, i guess we can atleast paste the questions here so that others who are interested can try to solve it.
-
Harshil_Patel_03b5f2 wrote: Write a program to pick out squarefree numbers from a given set of numbers. The criteria for a squarefree number is that it should not be a square value of its divisors and also its divisor should not be a sqaure value of its divisors. For example, 10 is square-free but 18 is not, as it is divisible by 9 = 32 .
There are two methods used in this program and they are getNoOfSquareFreeNumbers and getSquareFreeNumbers. The method getNoOfSquareFreeNumbers uses a range of integer values and returns a single integer value which is the count of square free numbers present. The second method getSquareFreeNumbers returns all the numbers that satisfy the criteria for sqare free number.
Example 1:
Input
from = 1
to = 10
Output
Function getNoOfSquareFreeNumbers return : 7
Function getSquareFreeNumbers returns : {1,2,3,5,6,7,10}
Explanation:In this example the input range of numbers is from 1 to 10. The numbers that are missing in the output are {4,8 and 9}. If we consider the integer 4 we can see that the divisor 2 when squared will result in 4. So it is not a sqarefree number. The same goes for 8 and 9.
Example 2:
Input
from = 4383
to = 4400
Output
Function getNoOfSquareFreeNumbers return : 11
Function getSquareFreeNumbers returns : {4385, 4386, 4387, 4389, 4390, 4391, 4393, 4395, 4397, 4398, 4399}
For C solutions
Header File : SquareFreeNumbers.h
Function Name : int getNoOfSquareFreeNumbers(int from, int to), int* getSquareFreeNumbers(int from, int to)
Directory Name : squarefreenumbers
File Name : SquareFreeNumbers.c
For C++ solutions
Header File : SquareFreeNumbers.h
Class Name : SquareFree
Function Name : int getNoOfSquareFreeNumbers(int from, int to), int* getSquareFreeNumbers(int from, int to)
Directory Name : squarefreenumbers
FileName : SquareFreeNumbers.cpp
#include"SquareFreeNumbers.h"
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
int isPerfectSquare(int);
int isSquareFree(int);
int isSquareFree(int no) {
int j=0;
for(j=2 ; j<=no ; j++) {
if(no%j==0) { // factor
if(isPerfectSquare(j)) { //Not square free
return 0;
}
}
}
return no;
}
int getNoOfSquareFreeNumbers(int from, int to) {
int i=0,j=0, cnt=0, flag=0;
for(flag=0, i=from ; i<=to ; i++) {
if(isSquareFree(i)) {
cnt++;
}
}
return cnt;
}
int* getSquareFreeNumbers(int from, int to) {
int *arr;
int i, cnt=0;
arr = (int *)malloc(sizeof(int) * (getNoOfSquareFreeNumbers(from, to)));
for(i=from ; i<=to ; i++) {
if(isSquareFree(i)) {
arr[cnt++]=i;
}
}
return arr;
}
int isPerfectSquare(int n) {
int i=1;
while( (i*i) != n) {
if((i*i) >= n) {
return 0;
}
i++;
}
return i;
}
void dsmain() {
int n,from=4383, to=4400, i, *arr;
from=1, to=10;
n=getNoOfSquareFreeNumbers(from, to);
arr = getSquareFreeNumbers(from, to);
printf("Total No of Square Free Numbers : %d\n",n);
printf("The square free numbers are :\n");
for(i=0 ; i<n ; i++) {
printf("%d ",arr);
}
} -
Varun_Modi_a59ed9 wrote: Now I have the answer to the 1st question which works perfectly... but the problem is in the 2nd question.. can someone help me out in the 2nd question ???
As i didnt had enough time left, i was not able to solve it,, but even now i m not able to get the logic that i should use to get the solution..
Sorry m8 my friend also got one of those question, it was a hard one, i still cant find out the logic of it -
Alright people, finally i hv cracked the problem.. I have derived the solution, and its so easy...
Does anyone wants to have the solution??? Now the solution is simple, but try it urself first.. If you are not able to do it, i will post the answer here... I will wait for 3 people to ask for the answer here, than i will post the answer...
Harshil will also get a good response to this thread, after all it was his idea to start this thread and where we all met -
When, you said about the multiple answers exist, I got a way to find a valid answer....
Though my code same output for the 1st example, for 2nd one it gives a different but a valid answer to the example... this can be extended to any question and it will give a valid answer if it exists...
Will surely like to know what logic you used for your code -
Ya guys, post the logic its becoming harder to wait
-
Hey buddy, I was not taunting or anything like that... Its nothing like that.. i m sorry if u felt so.. i was just highlighting the points of my code..
Can you post your code also??? -
First of all thanks varun for posting the code. I now finally have understood the logic after seeing the code, the logic seems to look like a piece of cake why the hell we wasn't able to solve such an easy question hehe
And one more thing i have to point ut guys. Please dont fight, we need to create a good and healthy community here -
@ harshil
u r right dude.....
v should not fight here,...we are the members ..
if we won't unite then Admins will take the advantage of this
-
@Varun, i have posted the question to that maze problem that you was requesting It was also a hard one, i cant find out the solution to it. Also one more problem is there about the BUS ROUTE, i will post that later, after we have done discussions on this MAZE problem.
-
Sure m8, let me try finding the image to that maze problem. I also think that the greedy approach can be used. The problem is that it will become to complex
-
OK here is the link to the maze image.
-
Thanks sanket for the Happy Numbers problem
and varun, on the first look the problem seems simple, but when we try to implement it we get stuck. the main problem i faced was how to make the computer know in which direction to go. Now to make it easy, suppose we assume that we want to ONLY move in right down direction, but then when i tried implementing my program got stuck in a loop cause when it shifted the control to another box in the maze image, it found out that the earlier box which we came from was the minimum, and hence it tried shifting the control to there so i guess we will have to keep track of what all places we visited, and if have already visited a place, then find the next minimum. -
Sanket, Thanks for the FLAMES problem and solution
Can you help us try solving the MAZE problem ? it too seems to be complicated. -
Maze problem .............solution .............
#include <stdio.h>
#include<alloc.h>
#include <conio.h>
int r = 4;
int c = 6;
int values[][20] = { { 5, 11, 11, 11, 11, 11},
{ 1, 11, 11, 11, 10, 11},
{ 1, 1, 11, 1 , 1 , 1 },
{ 11, 1, 1 , 1 , 10 ,1}};
int min(int a,int b);
int minimum(int arr[],int visited[],int n);
int makeCostMatrix(int r,int c,int arr[20][20],int *cost[400]);
int mazeMove(int r,int c,int values[][20]);int min(int a,int b)
{
return a<b?a:b;
}int minimum(int arr[],int visited[],int n)
{
int small=9999,i;
for(i=1;i<=n;i++)
{
if(visited==1)
continue;
if(arr<small)
small=arr;
}
for(i=1;i<=n;i++)
{
if(visited==1)
continue;
if(arr==small)
return i;
}
return 0;
}int makeCostMatrix(int r,int c,int arr[20][20],int *cost[400])
{
int cnt=0,i,j;
for(i=0;i<r;i++)
{
for(j=0;j<c;j++)
{
int nodeNo = i*c+j;
if(j+1<c) //next in row
{
cost[nodeNo][nodeNo+1]=arr[nodeNo/c][(nodeNo+1)%c];
cnt++;
}
if(j-1>=0) //prev in row
{
cost[nodeNo][nodeNo-1]=arr[(nodeNo-1)/c][(nodeNo)%c];
cnt++;
}
if(i+1<r) //down in col
{
cost[nodeNo][nodeNo+c]=arr[(nodeNo+c)/c][(nodeNo)%c];
cnt++;
}
if(i-1>=0) //up in col
{
cost[nodeNo][nodeNo-c]=arr[(nodeNo)/c][(nodeNo-c)%c];
cnt++;
}
}
}
return cnt/2;
}int mazeMove(int r,int c,int values[][20])
{
int i,j,k,l[400],path[400],pl=0,visited[400]={0},v;
int start=0,end=r*c-1,cnt=r*c-1;
int *cost[400];
for(i=0;i<400;i++)
cost = (int*)malloc(400);
for(i=0;i<r*c;i++)
for(j=0;j<r*c;j++)
cost[j]=9999;
makeCostMatrix(r,c,values,cost);
for(i=0;i<400;i++)
{
l=9999;
path=-1;
}
v=start;
visited[v]=1;
path[start]=0;
for(i=0;v!=end;i++)
{
for(j=0;j<=cnt;j++)
{
if(visited[j]==1)
continue;
l[j]=min(l[j],pl+cost[v][j]);
if(min(l[j],pl+cost[v][j])==pl+cost[v][j])
path[j]=v;
}
v=minimum(l,visited,cnt);
visited[v]=1;
pl=l[v];
}
for(k=0,i=end;i!=start
{
visited[k++]=path;
i=path;
}
return pl+values[0][0];
}void main()
{
clrscr();
printf("\n%d",mazeMove(r,c,values));
getch();
} -
Thanks dude for the code. It would be nice if you give the logic of your code, its a bit tricky
-
I think no one is interested anymore in that maze solution.
Lets post another question -
The above question is for the Block Counting Problem.
I guess its a hard one, lets see if anyone can solve it
I have many more questions if you guys want ....
