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