## Interview Question

**Country:**United States

```
findNthInSeries : N int
div4 = div7 = div28 = 0
if N >= 4
let div4 = N >> 2
if N >= 7
let div7 = N / 4
if N >= 28
let div28 = N /28
moveFurther = div4 + div7 - div28
divTest4 = 5 //00..0011
while moveFurther > 0
++N
if N % 28 == 0
{}
else if (N % 7 == 0) or (N & divTest == 0)
++N
--moveFurther
if N % 28 == 0
{}
else if (N % 7 == 0) or (N & divTest == 0)
++N
return N
```

2 changes i think:

div7 should be n/7

also divtest4 should be 3 and not 5(you wrote the correct binary equivalent!)

also i don't think its necessary for you to check for numbers being greater than 4,7,28

a check whetehr the number is greater than 0 in the beginning should be enough

```
int findNthInSeries(int n) {
int returnNum = 0;
for (int i = 1; i <= n; ++i) {
bool multOfFour = (i % 4 == 0);
bool multOfSeven = (i % 7 == 0);
if ((multOfFour && !multOfSeven) || (!multOfFour && multOfSeven)) { //XOR
returnNum += 2;
} else {
++returnNum;
}
}
return returnNum;
}
```

```
int findnth(int n)
{
int number = 1;
for(int i=0; i < n; i++)
{
while(number%4 == 0 || number%7 == 0)
{
number += 1;
}
number += 1;
}
return number-1;
}
```

/*Algorithm written by shashei kumar*/

package com.carrierCup;

public class gameCollision2 {

public static int numberToReturn(int num)

{

int iterator=1;

int count=0;

int next=1;

while(count!=num)

{

if((iterator%4)==0||(iterator%7)==0)

{

next=iterator+1;

}

else

{

next=iterator;

count++;

}

iterator++;

}

return next;

}

public static void main(String []a)

{

System.out.print(numberToReturn(10));

}

}

What is time complexity of your algorithm?

In other words, can it run for, say, n = 10^10;

Below I propose a faster algorithm:

Let sk(n) is the number of numbers that are skipped in range [1, n] by the rule.

sk(n) can be calculated in a constant time (?).

```
pseudo code:
find_Nth_Number(int n){
resNum = n; // init value
oldNum = n;
skipt = sk(n);
while(resNum - sk(resNum) <n){
oldNum = resNum;
resNum += skipt;
skipt = sk(resNum) - sk(oldNum);
};
return resNum;
};
```

Time complexity O(log n):

1. The number of skipped numbers in range [1, n] is O(n/k), where k is a constant greater than 1:

e.g., k = 1/ (1/4 + 1/7 - 1/28) = 2.8

2. Thus, the values of the variable "skipt" are decreasing as a geometric progression:

n/k , (n/k)/k, n/k^3, ...

This series converges to 0 after O(log n) times

3. Thus, the while loop is O(log n)

4. sk(n) can be calculated in constant time (?)

```
public class a
{
public static void main(String ...args)
{
System.out.println(function(10));
}
static int function(int n)
{
int answer=0;
int i=1;
while(i++<=n) {
answer++;
if (hasToMoveNumber(answer))
{
answer=iterateToNext(answer);
}
}
return answer;
}
static boolean hasToMoveNumber(int answer)
{
boolean divBy4 = answer%4==0 ;
boolean divBy7 = answer%7==0 ;
return (divBy4 || divBy7) &&(!(divBy4 && divBy7));
}
static int iterateToNext(int answer)
{
while(hasToMoveNumber(answer))
{
answer++;
}
return answer;
}
}
```

int find_nth_no(int n)

{

int div4=0;

int div7=0;

int div28=0;

int nn,mn,t4=1,t7=1,t28=1;

nn=n;

do {

if(div4!=t4){

t4=div4;

div4=nn/4;

t4 =div4 -t4;

} else { t4=0;}

if(div7!=t7) {

t7=div7;

div7=nn/7;

t7 = div7 -t7;

}else { t7=0; }

if(div28 !=t28) {

t28=div28;

div28=nn/28;

t28 = div28 - t28;

}else {t28=0;}

mn= (t4 + t7) - t28;

nn=nn+mn;

t4=nn/4;

t7=nn/7;

t28=nn/28;

if(div4==t4 && div7==t7 && div28==t28)

return nn;

}while (1);

}

```
int find_nth_no(int n)
{
int div4=0;
int div7=0;
int div28=0;
int nn,mn,t4=1,t7=1,t28=1;
nn=n;
do {
if(div4!=t4){
t4=div4;
div4=nn/4;
t4 =div4 -t4;
} else { t4=0;}
if(div7!=t7) {
t7=div7;
div7=nn/7;
t7 = div7 -t7;
}else { t7=0; }
if(div28 !=t28) {
t28=div28;
div28=nn/28;
t28 = div28 - t28;
}else {t28=0;}
mn= (t4 + t7) - t28;
nn=nn+mn;
t4=nn/4;
t7=nn/7;
t28=nn/28;
if(div4==t4 && div7==t7 && div28==t28)
return nn;
}while (1);
}
```

Let me know if i am incorrect somewhere

- aryanmain July 25, 2014