## Interview Question

Software Engineer / Developers**Country:**United States

logic is: the postions will be for first quardant of cordinate system : where 0<=x+y<=199 . hence due to symnetrry its multiplied by 4

@Kingmaker The logic is incorrect. {199, 0} is not the last coordinate the monkey can visit. {200, 0} is a valid coordinate as well.

Moreover, the second for loop should start from 1 and not 0. As of now, you add {0,0} 4 times in the count, which is incorrect.

I am planning to code using this logic as well to see where the correct answer leads too... Will post the code soon.

The question needs some clarifications. There are a few questions I would ask the interviewer. For e.g.

1. What count is required? All combinations of movements or the max path that the monkey can take.

Anyways, I "ASSUMED" that the count of all the possible coordinates is expected.

In that case, the answer to this is "87700".

Algorithm:

For each coordinate that the monkey is on, there are four possible routes that he can take. North (y+1), South (y-1), East (x+1) and West (x-1). Recursion seems to be the solution to take. The catch is the base condition that should be applied.

- If the sum of the coordinates is more than the limit, return.

- If this coordinate has already been visited, return.

Where should we store the coordinates that have been visited. I took the liberty of using a HashSet<string> type to store this. A string, because I wanted to make sure that the coordinate 'key' should be unique (There are other ways to get a unique key, but for the ease, I used a string key of the format "{0}:{1}", this arguments are the x and y value).

The rest is self explanatory. If you want to print-out the coordinates, just add another method to print-out all the values in the hashset.

The code is below.

```
public class MonkeyCoordinates
{
private HashSet<string> _accessibleCoordinates;
private int _limitSum;
public MonkeyCoordinates(int limitSum)
{
_limitSum = limitSum;
_accessibleCoordinates = new HashSet<string>();
}
public int GetAccessibleCoordinateCount()
{
_accessibleCoordinates.Clear();
Coordinate start = new Coordinate(0, 1);
AccessNorthEastQuadrantCoordinates(start);
return (_accessibleCoordinates.Count * 4);
}
private void AccessNorthEastQuadrantCoordinates(Coordinate current)
{
if (current.CoordinateSum > _limitSum) { return; }
if (!_accessibleCoordinates.Add(current.Key)) { return; }
// We have two directions to move. North and East.
AccessNorthEastQuadrantCoordinates(current.Move(Coordinate.Direction.East));
AccessNorthEastQuadrantCoordinates(current.Move(Coordinate.Direction.North));
}
}
internal sealed class Coordinate
{
private const string KEYFORMAT = "{0}:{1}";
internal enum Direction{North, South, East, West}
internal Coordinate(int x, int y)
{
XValue = x;
YValue = y;
Key = string.Format(KEYFORMAT, x, y);
CoordinateSum = Sum(x) + Sum(y);
}
internal int XValue { get; set; }
internal int YValue { get; set; }
internal string Key { get; set; }
internal int CoordinateSum { get; set; }
internal Coordinate Move(Direction direction)
{
int x = XValue;
int y = YValue;
switch (direction)
{
case Direction.East:
x += 1;
break;
case Direction.West:
x -= 1;
break;
case Direction.North:
y += 1;
break;
case Direction.South:
default:
y -= 1;
break;
}
return new Coordinate(x, y);
}
private int Sum(int val)
{
val = Math.Abs(val);
int sum = 0;
while (val > 0)
{
sum += val % 10;
val = val / 10;
}
return sum;
}
}
```

Please note the following:

1. The code does not have error checks.

2. There is a possiblity of a stack overflow if the limit sum is really high.

3. This is not an optimized solution. We could reduce it to 1/4th by processing only one quadrant and one axis. The result can then be multiplied by 4. If the starting coordinate needs to be included, add 1 to the result.

I agree and that is why I listed the drawbacks of the solution.

I did find some bugs in my solution and have hence fixed it in the original code. I have also changed the solution to calculate only one quadrant (North-East) and then multiply the solution by 4. The result is "87700". This is exluding the starting coordinate of {0,0}.

The correct answer is "102485". The only logic that has changed in my code [method GetAccessibleCoordinateCount] is to calculate the whole quadrant and then subtract common coordinates of one axis (to not be counted 4 times) and then add the start element.

```
public class MonkeyCoordinates
{
private HashSet<string> _accessibleCoordinates;
private int _limitSum;
public MonkeyCoordinates(int limitSum)
{
_limitSum = limitSum;
_accessibleCoordinates = new HashSet<string>();
}
public int GetAccessibleCoordinateCount()
{
_accessibleCoordinates.Clear();
Coordinate start = new Coordinate(0, 0);
AccessNorthEastQuadrantCoordinates(start);
// Remove the start element.
_accessibleCoordinates.Remove(start.Key);
// Get the count of coordinates on one of the axis.
string[] commonCoordinates = (from northEastCoordinate in _accessibleCoordinates
where (northEastCoordinate.StartsWith("0:"))
select northEastCoordinate).ToArray();
int count = 1 + ((_accessibleCoordinates.Count - commonCoordinates.Length) * 4);
return count * 4;
}
private void AccessNorthEastQuadrantCoordinates(Coordinate current)
{
if (current.CoordinateSum > _limitSum)
{
return;
}
if (!_accessibleCoordinates.Add(current.Key))
{
return;
}
// We have two directions to move. North and East.
Coordinate east = current.Move(Coordinate.Direction.East);
AccessNorthEastQuadrantCoordinates(east);
Coordinate north = current.Move(Coordinate.Direction.North);
AccessNorthEastQuadrantCoordinates(north);
}
}
internal sealed class Coordinate
{
private const string KEYFORMAT = "{0}:{1}";
internal enum Direction
{
North,
South,
East,
West
}
internal Coordinate(int x, int y)
{
XValue = x;
YValue = y;
Key = string.Format(KEYFORMAT, x, y);
CoordinateSum = Sum(x) + Sum(y);
}
internal int XValue
{
get;
set;
}
internal int YValue
{
get;
set;
}
internal string Key
{
get;
set;
}
internal int CoordinateSum
{
get;
set;
}
internal Coordinate Move(Direction direction)
{
int x = XValue;
int y = YValue;
switch (direction)
{
case Direction.East:
x += 1;
break;
case Direction.West:
x -= 1;
break;
case Direction.North:
y += 1;
break;
case Direction.South:
default:
y -= 1;
break;
}
return new Coordinate(x, y);
}
private int Sum(int val)
{
val = Math.Abs(val);
int sum = 0;
while (val > 0)
{
sum += val % 10;
val = val / 10;
}
return sum;
}
}
```

On some site I found that the confirmed answer is - 102485 and I followed the logic. Below is the C++ code. However I am only getting 39 as the answer.

```
#include<stdio.h>
#include <iostream>
#include <map>
#include <utility> // make_pair
#include <string.h>
#include <sstream>
using namespace std;
typedef std::map<int, int> MapType;
class assgnt
{
private:
//MapType my_map;
public:
bool isGoodPoint(int x, int y);
MapType addGoodNeighbours(int x, int y, std::map<int, int> MapType);
bool check_pair(int x, int y, std::map<int, int> MapType);
};
inline bool assgnt::isGoodPoint(int x, int y)
{
string xs, ys;
stringstream xout, yout;
int xsum=0, ysum=0;
xout << abs(x);
yout << abs(y);
xs = xout.str();
ys = yout.str();
for each (char c in xs)
{
xsum = xsum + (c - '0');
}
for each (char c in ys)
{
ysum = ysum + (c - '0');
}
if (xsum+ysum <= 19)
return true;
else
return false;
}
inline bool assgnt::check_pair(int x, int y, MapType my_map)
{
//MapType my_map;
MapType::iterator iter = my_map.begin();
iter = my_map.find(x);
if (iter != my_map.end())
{
int num = iter->second;
if(num == y)
{
//std::cout << "Value is found: " << iter->second << '\n';
return true;
}
else
{
//std::cout << "Value not found: ";
return false;
}
}
/* else
std::cout << "Key is not in my_map" << '\n';*/
return false;
}
inline MapType assgnt::addGoodNeighbours(int x, int y, MapType my_map)
{
//MapType my_map;
if(isGoodPoint(x+1,y))
{
if(!check_pair(x+1, y, my_map))
{
my_map.insert(std::pair<int, int>(x+1, y));
}
}
if(isGoodPoint(x-1,y))
{
if(!check_pair(x-1, y, my_map))
{
my_map.insert(std::pair<int, int>(x-1, y));
}
}
if(isGoodPoint(x, y+1))
{
if(!check_pair(x, y+1, my_map))
{
my_map.insert(std::pair<int, int>(x, y+1));
}
}
if(isGoodPoint(x,y-1))
{
if(!check_pair(x, y-1, my_map))
{
my_map.insert(std::pair<int, int>(x, y-1));
}
}
return my_map;
//std::cout << "Size of my_map: " << my_map.size() << '\n';
}
int main()
{
MapType my_map;
assgnt obj1;
// insert elements using insert function
my_map.insert(std::pair<int, int>(0, 0));
int i=0;
while (true)
{
my_map = obj1.addGoodNeighbours(i, i, my_map);
i=i+1;
if (i >= int(my_map.size()))
break;
else
continue;
}
std::cout << "Size of my_map: " << my_map.size() << '\n';
// my_map.clear();
```

}

Most of the logic seemed to be the one that I coded with. The only issue that I see is the while loop in Main.

```
int i=0;
while (true)
{
my_map = obj1.addGoodNeighbours(i, i, my_map);
i=i+1;
if (i >= int(my_map.size()))
{
break;
}
else
{
continue;
}
std::cout << "Size of my_map: " << my_map.size() << '\n';
}
```

After adding good neighbors, you are incrementing i by 1. Therefore, you are moving diagonally in the map.

i.e. Starting Point {0,0}

{1,1}

{2,2}

{3,3}

This logic seems to be totally incorrect. The more logical solution with this approach should be (algorithm).

- Add the starting node to the map.

- While(current position does not reach maps end)

- get the node (current position)

- Add valid members to the map.

- Increment current poition.

- the size of the map should have the number of nodes.

I tried using 2 for loops in place of while loop, but still it didn't work out. Would you please check and comment:

for(int i=0; i < int(my_map.size()) ; i++)

{

for(int j=0; j < int(my_map.size()) ; j++)

{

my_map = obj1.addGoodNeighbours(i, j, my_map);

}

}

Why do you need 2 for loops?

I haven't worked with C++ much, but will give it a shot in terms of algorithm.

Moreover, I don't think that using the collection size in the for loop is a good practice when that collection is being modified in the loop itself.

Anyways, here is what I think should be the solution.

```
// Please insert a start coordinate {0,0} in the map before the for loop.
for(int index = 0; index < int(my_map.Size()); ++index)
{
// Get the coordinate at the current index.
// Please add a method to get the value at a desired index in the map.
mapCoordinate = GetElementAtIndex(my_map, index);
// For this mapCoordinate.
my_map = AddGoodNeighbors(mapCoordinate.x, mapCoordinate.y, my_map);
}
// once you are out of the loop, you should have the map of all possible coordinates.
int count = int(my_map.Size());
```

i think the answer is 102486

```
#include<iostream>
#include<conio.h>
using namespace std;
int a[10000][10000]={0};
int val=0;
bool caldigit(int a,int b)
{
int sum=0,i=a,j=b;
if(i<0)
{
i*=-1;
//cout<<"the i is "<<a<<endl;
}
if(j<0)
{
j*=-1;
//cout<<"the j is "<<b<<endl;
}
while(i)
{
sum=sum+(i%10);
i/=10;
}
while(j)
{
sum=sum+(j%10);
j/=10;
}
if(sum<=19)
{
//cout<<"S the value is "<<val<<" i "<<a<<" j "<<b<<" the sum is "<<sum<<endl;
return true;
}
else
{
//cout<<"F the value is "<<val<<" i "<<a<<" j "<<b<<endl;
return false;
}
}
void move(int i,int j)
{
if(i<4999&&j<4999&&i>=-5000&&j>=-5000)
{
//cout<<"the value is "<<val<<endl;
if((a[i+5000][j+1+5000]==0)&&(caldigit(i,j+1)))
{
val++;
a[i+5000][j+1+5000]=1;
//cout<<" first the i "<<i<<" j "<<j+1<<endl;
move(i,j+1);
}
if((a[i+1+5000][j+5000]==0)&&(caldigit(i+1,j)))
{
val++;
a[i+1+5000][j+5000]=1;
//cout<<" second the i "<<i+1<<" j "<<j<<endl;
move(i+1,j);
}
if((a[i+5000][j-1+5000]==0)&&(caldigit(i,j-1)))
{
val++;
a[i+5000][j-1+5000]=1;
//cout<<" third the i "<<i<<" j "<<j-1<<endl;
move(i,j-1);
}
if((a[i-1+5000][j+5000]==0)&&(caldigit(i-1,j)))
{
val++;
a[i-1+5000][j+5000]=1;
//cout<<" forth the i "<<i-1<<" j "<<j<<endl;
move(i-1,j);
}
}
else
{
cout<<" the i "<<i<<" j "<<j<<endl;
}
//cout<<" function exit "<<val<<endl;
}
int main()
{
int i=0,j=0;
move(0,0);
val++;
cout<<"the value is "<<val<<endl;
//for(i=4700;i<5300;i++)
// {
// for(j=4700;j<5300;j++)
// {
// cout<<""<<a[i][j];
// }
// cout<<""<<endl;
// }
getch();
}
```

This problem can be modified as:

1) Monkey can only walk right or up, one step at a time.

2) For the origin(0,0), count it only once.

3) For all the points on x-axis or y-axis, count them twice.

4) For all other points, count them 4 times.

int arr[1024][1024] = {0};

void AccessibleCoordinates(int x, int y, int &count)

{

if(arr[x][y] == 1) return; //already traversed

else arr[x][y] = 1;

if(SumOfDigits(x)+SumOfDigits(y) > 19) {return;}

if(x==0 && y==0) {count += 1;}

else if(x==0 || y==0) {count += 2;}

else {count += 4;}

AccessibleCoordinates(x+1, y, count);

AccessibleCoordinates(x, y+1, count);

}

@Nayan Good solution Nayan.

I generalized it a bit for the array size. Now, you can pass in any sum limit and this will work (obviously not if the limit sum causes a MemoryOutOfRangeException:)).

```
public static int GetPossibleCoordinates(int limitSum)
{
Stack<Coordinate> coordinates = new Stack<Coordinate>();
coordinates.Push(new Coordinate(0, 0));
return GetQuadrantCoordinates(coordinates, limitSum);
}
public static int GetQuadrantCoordinates(Stack<Coordinate> coordinates, int limitSum)
{
int count = 0;
int arraySize = GetRequiredArraySize(limitSum) + 1;
int[,] accessibleCoordinates = new int[arraySize, arraySize];
while (coordinates.Count != 0)
{
Coordinate current = coordinates.Pop();
int x = current.XValue;
int y = current.YValue;
if (accessibleCoordinates[x, y] == 1)
{
continue;
}
else
{
accessibleCoordinates[x, y] = 1;
}
if ((GetSumOfDigits(x) + GetSumOfDigits(y)) > limitSum)
{
continue;
}
if (x == 0 && y == 0)
{
count += 1;
}
else if (x == 0 || y == 0)
{
count += 2;
}
else
{
count += 4;
}
// Add elements to stack, it not already.
if(accessibleCoordinates[x + 1, y] != 1)
{
coordinates.Push(new Coordinate(x + 1, y));
}
if (accessibleCoordinates[x, y + 1] != 1)
{
coordinates.Push(new Coordinate(x, y + 1));
}
}
return count;
}
public static int GetSumOfDigits(int num)
{
int sum = 0;
num = Math.Abs(num);
while (num > 0)
{
sum += num % 10;
num /= 10;
}
return sum;
}
public static int GetRequiredArraySize(int limitSum)
{
int requiredSize = 0;
while (limitSum > 9)
{
limitSum -= 9;
requiredSize = (10 * requiredSize) + 9;
}
requiredSize = ((limitSum + 1) * (requiredSize + 1)) + requiredSize;
return requiredSize;
}
```

Answer is 102485

#include<iostream>

#include<set>

#include<cmath>

using namespace std;

int sumDig(int x) {

x = abs(x);

int sum = 0;

while (x) sum += x % 10, x /= 10;

return sum;

}

bool valid(int x, int y) {

return (sumDig(x) + sumDig(y) <= 19);

}

void travel(int x, int y, set<pair<int, int> >& s) {

for (int i = -1; i < 2; ++i) {

for (int j = -1; j < 2; ++j) {

if (abs(i + j ) == 1) {

int x1 = x + i;

int y1 = y + j;

if (valid(x1, y1) && s.find(make_pair(x1,y1)) == s.end()) {

s.insert(make_pair(x1, y1));

travel(x1, y1, s);

}

}

}

}

}

int main() {

set<pair<int,int> > s;

s.insert(make_pair(0,0));

travel(0,0,s);

cout << s.size();

return 0;

}

Answer is 102485

```
#include<iostream>
#include<set>
#include<cmath>
using namespace std;
int sumDig(int x) {
x = abs(x);
int sum = 0;
while (x) sum += x % 10, x /= 10;
return sum;
}
bool valid(int x, int y) {
return (sumDig(x) + sumDig(y) <= 19);
}
void travel(int x, int y, set<pair<int, int> >& s) {
for (int i = -1; i < 2; ++i) {
for (int j = -1; j < 2; ++j) {
if (abs(i + j ) == 1) {
int x1 = x + i;
int y1 = y + j;
if (valid(x1, y1) && s.find(make_pair(x1,y1)) == s.end()) {
s.insert(make_pair(x1, y1));
travel(x1, y1, s);
}
}
}
}
}
int main() {
set<pair<int,int> > s;
s.insert(make_pair(0,0));
travel(0,0,s);
cout << s.size();
return 0;
}
```

This has some issues. It seems you allow the monkey move from (18,0) to (20,0). But it actually can't because there is no way the monkey can jump from (18,0) to (20,0) without hitting the barrier. I will say the total number of points is the number of points in the square of (-18,0), (0, -18), (18, 0), and (0, 18), so it is (18*sqrt(2)) ^ 2 = 648

I may be wrong, but I think we can answer this without writing code. I was thinking on these lines. Lets consider monkey is on (0,0) and it can move only in quadrant I ( i.e x and y co-ordinates are all +ve ).

So if monkey is on point(0,0) then lets assume he is just moving to right until it hits maximum at (1927,0) since sum of digits is 19. So for now it has travelled 1928 points. It cannot travel up but has to go 1 left position and then 1 up position to (1926,1). Now on that horizontal line it is free to travel left until it hits point (0,1). For that horizontal line it has travelled 1927 points. Using same iteration it will travel up on Y axis until it hits (0,1927). and every level number of points it travels is one less than below line. If we plot points it will become like equilateral triangle with co-ordinates (0,0) , (0,1927) and (1927,0). Or the total number of points in that triangle are summation of points 1,2,3,..1928. i.e n(n+1)/2 formula gives 1928*1929/2= 1859556.

Similarly we can see its replica for rest of 3 quadrants. so total no of points is 7438224. But while doing for all 4 quads we are duplicating the values on the x and y axis so we need to subtract it. hence total points should be 7438224 - 4(1928) = 7430512.

Hope it makes sense.

```
import java.util.HashSet;
import java.util.Iterator;
public class MonkeyCoordinates {
private static String KEYFORMAT = "(%d:%d)";
private HashSet<String> accessCoords;
private static int commonCoordsCount=0;
private int maxSum;
private enum Direction {
NORTH, SOUTH, EAST, WEST;
}
public MonkeyCoordinates(int sum) {
maxSum = sum;
accessCoords = new HashSet<String>();
}
public int getAccessCoordsCount() {
accessCoords.clear();
Coordinate start = new Coordinate(0, 0);
accessNorthEastQuadCoords(start);
accessCoords.remove(start.key);
Iterator<String> it = accessCoords.iterator();
while(it.hasNext()) {
String common = it.next();
if (common.startsWith("(0:")) {
commonCoordsCount++;
}
//System.out.println(it.next());
}
return (1 + (accessCoords.size() - commonCoordsCount) * 4);
}
private void accessNorthEastQuadCoords(Coordinate current) {
if (current.coordSum > maxSum) {
return;
}
if (!accessCoords.add(current.key)) {
return;
}
accessNorthEastQuadCoords(current.move(Direction.EAST));
accessNorthEastQuadCoords(current.move(Direction.NORTH));
}
private class Coordinate {
private int xValue, yValue;
String key;
public int coordSum;
public int getxValue() {
return xValue;
}
public void setxValue(int xValue) {
this.xValue = xValue;
}
public int getyValue() {
return yValue;
}
public void setyValue(int yValue) {
this.yValue = yValue;
}
public Coordinate(int x, int y) {
setxValue(x);
setyValue(y);
key = String.format(KEYFORMAT, getxValue(), getyValue());
coordSum = sum(x) + sum(y);
}
Coordinate move(Direction direction) {
int x = getxValue();
int y = getyValue();
switch (direction) {
case EAST:
x++;
break;
case WEST:
x--;
break;
case NORTH:
y++;
break;
case SOUTH:
default:
y--;
break;
}
return new Coordinate(x, y);
}
private int sum(int val) {
val = Math.abs(val);
int sum = 0;
while (val > 0) {
sum += val % 10;
val = val / 10;
}
return sum;
}
}
public static void main(String[] args) {
MonkeyCoordinates mon = new MonkeyCoordinates(19);
System.out.println("Coordinates accessible by Monkey is " + mon.getAccessCoordsCount());
}
}
```

Here is complete solution.

comment if you disagree.

//

// File: Monkey_points.cpp

//

/*******prints total number of points monkey can access ***************/

/*******print all the points monkey can access in separate points.txt file ******/

/********************************************************************************/

#include "stdafx.h"

#include <fstream>

#include <iostream>

using namespace std;

int coordinates(int x,int y)

{

int totalcount=0;

ofstream the_file;

the_file.open("points.txt");

for ( int i=(-x); i<x; i++)

{

for ( int j=(-y); j <= y; j++)

{

if ( (i + abs(j) ) <= 19)

{

cout<<i<<" "<<j<<endl;

the_file<<i<<" ";

the_file<<j<<endl;

totalcount++;

}

}

}

for ( int i=(-y); i<=y; i++)

{

for ( int j=(-x); j < y; j++)

{

if ( (i + abs(j) ) <= 19)

{

cout<<j<<" "<<i<<endl;

the_file<<j<<" ";

the_file<<i<<endl;

totalcount++;

}

}

}

the_file.close();

return totalcount;

}

int _tmain(int argc, int argv[])

{

int totalcount=0;

cout<<"Printing Monkey Access points"<<endl;

totalcount = coordinates(19,19);

cout<<"total points monkey can access is "<<totalcount<<endl;

getchar();

return 0;

}

>> Output

total points monkey can access is 2261

program :-

#include<iostream.h>

#include<math.h>

class point

{

public:

int xco;

int yco;

point()

{

xco=0;

yco=0;

}

point(int x,int y) : xco(x) , yco(y)

{

}

bool isaccesible()

{

int lxco=abs(xco);

int lyco=abs(yco);

int sum=0;

while(lxco)

{

sum=sum+(lxco%10);

lxco=lxco/10;

}

while(lyco)

{

sum=sum+(lyco%10);

lyco=lyco/10;

}

if(sum<=19)

return true;

else

return false;

}

point operator + (point& p)

{

int lxco=xco+p.xco;

int lyco=yco+p.yco;

return(point(lxco,lyco));

}

void display ()

{

cout << " xco " << xco << " yco " << yco << endl;

}

bool operator ==(point & p)

{

if(xco==p.xco && yco==p.yco)

return true;

else

return false;

}

};

template <class datatype>

class myqueue

{

public:

int count;

datatype arr_of_datatype[500000];

myqueue<datatype> ()

{

count=0;

}

void pop()

{

if(count<1)

cout << " Queue is empty " << endl;

else

{

//delete(arr_of_datatype[0]);

for(int i=0;i<count-1;i++)

{

arr_of_datatype[i]=arr_of_datatype[i+1];

}

count--;

}

}

void push(datatype myqdt)

{

if(count>499999)

cout << " Queue is full " << endl;

else

{

arr_of_datatype[count]=myqdt;

count++;

}

}

datatype front()

{

if(count>0)

return arr_of_datatype[0];

else

cout << " Queue is empty " << endl;

}

datatype* pfront()

{

if(count>0)

return (&arr_of_datatype[0]);

else

cout << " Queue is empty " << endl;

}

datatype operator [](int k)

{

if(count>0 && k<count)

return arr_of_datatype[k];

else

cout << " Queue is empty " << endl;

}

int size()

{

return count;

}

bool empty()

{

if(count==0)

return true;

else

return false;

}

};

int iisnotadded[1000][1000]={1};

int main()

{

for(int i=0;i<1000;i++)

for(int j=0;j<1000;j++)

iisnotadded[i][j]=1;

int tpop=0,count=0,k,validmoves[]={1,0,-1,0,0,1,0,-1};

myqueue<point> myQ;

point start(0,0);

if(start.isaccesible() )

{

myQ.push(start);

iisnotadded[start.xco+500][start.yco+500]=0;

count++;

}

while(myQ.count!=0)

{

cout << " myQ.count " << myQ.count << " current count " << count << " total pop " << tpop << endl;

for(int j=0;j<4;j++)

{

point temp;

temp=myQ.front() + point(validmoves[2*j],validmoves[(2*j)+1]);

if(iisnotadded[temp.xco+500][temp.yco+500])

{

if(temp.isaccesible() )

{

count++;

myQ.push(temp);

iisnotadded[temp.xco+500][temp.yco+500]=0;

temp.display();

}

}

}

delete(myQ.pfront() );

myQ.pop();

tpop++;

}

cout << " final : COUNT " << count << endl;

}

output :- final : COUNT 102485

```
public static void main(String[] args) {
System.out.println(getCount());
}
public static int getCount() {
int count = 0;
int x = 0, y = 0;
for (int i = 0; i < 199; i++) {
for (int j = 0; j < 199; j++) {
if (sum(i) + sum(j) < 19) {
System.out.println(" i :" + i + " j :" + j);
count++;
}
}
}
return count;
}
private static int sum(int num) {
int sum = 0;
num = Math.abs(num);
while (num > 0) {
sum += num % 10;
num = num / 10;
}
return sum;
}
```

Total Count would be 18670.

int findnumberofpositions()

- Kingmaker March 18, 2012{

int count = 0;

for(int i =0 ; i<=199 ;i++)

{

for(int j =0 ; j<=199 ;j++)

{

if(getsumofdigit(i)+getsumofdigit(j) <= 19) // getsumofdigit function returns sum of // digit of input number

count++;

}

}

return count*4;

}

int getsumofdigit (int n)

{

int count-0;

while(n>0)

{

count+= n%10;

n=n/10;

}

}