ADP Interview Question Developer Program Engineers
Country: United States
Nice!
However, we should probably ask the interviewer what is the definition of the "next nearest" here. Is it the next lucky number that is greater than the given number? Or it is the next lucky number that is greater than or equal to that number.
static int GetNeareastLuckyNum(int num)
{
int length = GetNumLength(num);
int small = GenerateNum(length, 4);
int big = GenerateNum(length, 7);
if (num < small)
{
return small;
}
if (num >= big)
{
return GenerateNum(length + 1, 4);
}
List<int> ll = GetLuckyNumList(length);
int[] a = ll.OrderBy(x => x).ToArray();
int i = 0;
for (; i < a.Length; i++)
{
if (num < a[i])
{
break;
}
}
return a[i];
}
static List<int> GetLuckyNumList(int length)
{
List<int> list = new List<int>();
List<int> nlist = new List<int>();
while (length > 0)
{
if (list.Count != 0)
{
foreach (var item in list)
{
nlist.Add(item * 10 + 7);
nlist.Add(item * 10 + 4);
}
list.Clear();
}
else if (nlist.Count != 0)
{
foreach (var item in nlist)
{
list.Add(item * 10 + 7);
list.Add(item * 10 + 4);
}
nlist.Clear();
}
else
{
list.Add(7);
list.Add(4);
}
--length;
}
return nlist.Count > list.Count ? nlist : list;
}
static int GenerateNum(int length, int num)
{
int newNum = num;
while (length > 1)
{
newNum = newNum * 10 + num;
--length;
}
return newNum;
}
static int GetNumLength(int num)
{
if (num < 0)
{
return -1;
}
int length = 1;
while (num / 10 > 0)
{
++length;
num /= 10;
}
return length;
}
}
get the length of the number
First get the smallest and biggest one lucky numbers in the length of the number.
if the number is smaller than the smallest one, return smallest one
if the number is bigger or equal to the biggest one, return the smallest lucky number of length+1
else the number is between smallest and biggest lucky numbers, we can get all the lucky numbers in the length, then go through all the lucky numbers, find the first lucky number that is bigger than the number.
Following logic should work i guess.
oldnum = num
newnum = num;
Move from MSD(most significant Digit) to LSD(Least significant Digit)
If (current_digit <= 4)
{
replace(num, current_digit, 4);
newnum = num;
}
else
{
if ((newnum - oldnum) < 0)
replace(num, current_digit, 7);
else replace(num, current_digit, 4);
newnum = num;
}
replace() replaces in num, the digit at current location with 4 or 7(as mentioned, after current).
As I did not find any generic answer, I coded the following in c#. I already spent a couple of hours on it, so don't mind the ugly code
// It will return the same number, if the input number is a magic number
static int GetNextLuckyNumber(int n) {
int[] luckyDigits = { 4, 7 }; // maintain ascending order - 0 not supported
List<int> digits = getDigitsFromNumber(n);
List<int> luckyNumber = new List<int>();
// Let's traverse from left to right, digit-by-digit and find the smallest number larger than 'n'
for (int i = 0; i < digits.Count; ++i) {
int d = digits[i];
foreach (int lucky in luckyDigits) {
if (d < lucky) {
luckyNumber.Add(lucky);
goto outside_outer_for;
} else if (d == lucky) {
luckyNumber.Add(lucky);
break;
}
}
// if we could not find the digit to add, that means our generated lucky number is already smaller than 'n'
// so we backtrack and increment more significant digits
if (luckyNumber.Count - 1 < i) {
while (true) {
--i;
if (i < 0) // the lucky number is larger than the largest lucky number with same number of digits as 'n'
return getNumberFromDigits(luckyDigits[0], digits.Count + 1);
int newLuckyNumber = getNextDigit(luckyNumber[i], luckyDigits);
if (newLuckyNumber == -1)
luckyNumber.RemoveAt(i);
else {
luckyNumber[i] = newLuckyNumber;
goto outside_outer_for;
}
}
}
}
outside_outer_for:
// if we got out from goto, we need to fill the remaining numbers with the min
while (luckyNumber.Count < digits.Count)
luckyNumber.Add(luckyDigits[0]);
return getNumberFromDigits(luckyNumber);
}
// get the next higher lucky digit
static int getNextDigit(int digit, int []luckyDigits) {
for (int i = 0; i < luckyDigits.Length; ++i) {
if (luckyDigits[i] > digit)
return luckyDigits[i];
}
return -1;
}
// create a number with 'digit' repeated 'count' times
static int getNumberFromDigits(int digit, int count) {
int max = 0;
for (int i = 0; i < count; ++i)
max = max * 10 + digit;
return max;
}
// create a number from the specified digits
static int getNumberFromDigits(List<int> digits) {
int num = 0;
for (int i = 0; i < digits.Count; ++i)
num = num * 10 + digits[i];
return num;
}
// break a number into digits
static List<int> getDigitsFromNumber(int n) {
List<int> digits = new List<int>();
while (n != 0) {
digits.Add(n % 10);
n /= 10;
}
digits.Reverse();
return digits;
}
#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
int ln=0;
int x=10;
while(n!=0)
{
int a=n%10;
if(a<=4) ln=4*x+ln;
else ln=7*x+ln;
n=n/10;
x=x*10;
}
ln=ln/10;
cout<<ln;
}
1 #!/usr/bin/python
2
3 import sys
4
5 # get number
6 l_input = sys.argv[1]
7 print l_input
8
9 l_output = ""
10 l_carry = 0
// reverse string
12 l_input = l_input[::-1]
13 print l_input
14 for i in l_input:
15 if int(i) > 7:
16 l_output = l_output + "4"
17 l_carry = 1
18 elif int(i) == 7 and l_carry == 1:
19 l_output = l_output + "4"
20 l_carry = 1
21 elif int(i) > 4:
22 l_output = l_output + "7"
23 l_carry = 0
24 elif int(i) == 4 and l_carry == 1:
25 l_carry = 0
26 l_output = l_output + "7"
27 else:
28 l_output = l_output + "4"
29 l_carry = 0
30
31 if l_carry == 1:
32 l_output = l_output + "4"
33
34 l_output = l_output[::-1]
35 print l_output
Logic is simple goes from LSD to MSD if number is greater than 7 make it 4 and make the carry 1 , carry is cleared if next digit goes from < 4 to 4 or < 7 to 7 but if it is greater than 7 carry is carry forwarded to next and so on. if there is carry at the end most significant digit "4" is added. This seems to work for all if next lucky number is equal to or more than the given number
public class Lucky {
public static void main(String[] args) {
System.out.println(findNext(1004));
}
private static int findNext(int N) {
String s = Integer.toString(N);
char[] arr = s.toCharArray();
for (int i = 0 ; i < arr.length; i++) {
int num = (int) ( arr[i] - '0');
if (num == 4 || num == 7) continue;
if (num < 4 || num > 7) {
arr[i] = '0' + 4;
}
else arr[i] = '0' + 7;
}
return Integer.parseInt(new String(arr));
}
}
This does not work. issue is that if the char is 8 or 9, then you need to add 1 to the higher char.
Here is my solution:
public class Scratch {
public static int luckNumber(int number){
return lucknum(number, 0, 0);
}
private static int lucknum(int num, int total, int index){
int remainder = num % 10;
int leftover = num / 10;
if(remainder <= 4){
remainder = 4;
}else if(remainder <=7){
remainder = 7;
}else if(remainder >7){
remainder = 4;
leftover +=1; // this is the critical, carry 1 to higher digit.
}
total += remainder * (int)Math.pow(10, index);
if(leftover > 0){
total = lucknum(leftover, total, ++index);
}
return total;
}
}
This works for me:
public class FoursAndSevens {
public static void main(String[] args) {
String userNum = "1234"; //to be read thru user input
//get the digits count from the input
int digitsCount = 0;
for (int i=1; i<=userNum.length(); i++){
++digitsCount;
}
// figure out the max number in the digit range (9999 in iur example)
String max = "";
for(int i=0; i<digitsCount; i++){
max = max + "9";
}
System.out.println(getLucky(userNum, max));
}
private static int getLucky(String userNum, String max) {
// the range is: userNum to max digit (1234 - 9999 in our example)
for(Integer i= Integer.parseInt(userNum); i<= Integer.parseInt(max); i++){
char[] digits = i.toString().toCharArray();
boolean isLuckyNum = true;
for (char c : digits) {
// ignore the number if it has any digit other than 4 and 7
if(c == '4' || c == '7'){
continue;
}else{
isLuckyNum = false;
break;
}
}
// if you reach here, that means you got a lucky number, but check it that is not the input number itself (like 4444 or 7777)
isLuckyNum = isLuckyNum && (Integer.parseInt(userNum) != i);
if(isLuckyNum){
return i;
}
}
// increase the max range if you reach here (eg: in case of 7777, the next luck no. should be 44444, so range is now - 9999 to 99999)
return getLucky(max, max + "9");
}
}
first of all we take an infinite loop in which we are increasing the input by one in every loop n we take another loop inside first loop in which we check weather the no comprises of 4 and 7 with the help of " % and / " then we use break statement if we find the number which we required n after that by using some logic we also break the outermost loop and print out the number....
using 0 to represent 4, 1 to represent 7.
say x is n digit iterate from 00..0(n digits) to 11..1(n digits),
and convert binary to lucky number and compare to x
if no number is larger than x, increase one digit add test again.
e.g. 43 is 2 digits, iterate from 00 to 11, as a result 01 (represents 47) > 43, the next lucky number is found.
public static int nextLuckyNumber(int x) {
int digits = 0;
for (int n = x; n > 0; n /= 10) digits++;
// start from the digit of x
while (true) {
for (int i = 0; i < (1 << digits); i++) {
int lucky = 0;
// generate candidate lucky number and compare with x
for (int k = digits - 1; k >= 0; k--) {
if (((1 << k) & i) == 0) lucky = lucky * 10 + 4;
else lucky = lucky * 10 + 7;
}
if (lucky > x) return lucky;
}
digits++;
}
}
1. If the input is 77...7 then output 444...44 with an extra digit 4;
- ninhnnsoc April 18, 20142. If the input is a lucky number already: change the last digit 4 in the input into digit 7, and return;
3. If the input is not a lucky number:
Let d be the first un-lucky digit. So the input S can be represented as:
S = lucky_part + d + remain_part
Calculate the next lucky number N as:
if d<4: N = lucky_part + 4 + 44..4
if d<7: N = lucky_part + 7 + 44..4
if d>7: N = nextLuckyNumberOf(lucky_part) + 4 + 44...4
where 44..4 has same length as remain_part
EDITED:
I missed a case: the next lucky number of empty string is '4'