Iron Mountain Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
Use Bit wise shifting and division at the same time to get the 4 digit number in a loop and find the MAX one..
10 digit shift 0 bit divided by 1000000 --> First for digit number
10 Digit shift 1 bit divided by 100000 --> 2nd to 5th digit number
10 Digit shift 2 bit divided by 10000 --> 3nd to 6th digit number
and so on ..
Compare every number to MAX and if greater then MAX assign it to MAX.
This is my logic..
#include <stdio.h>
#include <conio.h>
int main()
{
long long number=7654932810;
long long i, k, j=10000, MAX=0, NUM=0, temp, temp1;
for(i=0;i<7;i++)
{
NUM=(number>>i);
for(k=0;k<i;k++)
{
NUM=NUM/5;
}
temp=(NUM/j);
temp1= NUM - temp*j;
if(MAX<temp1)
MAX=temp1;
}
printf("MAX=%lld",MAX);
getch();
}
Can be easily done by comparing the numbers rather than their integer value as suggested in other posts downvoted above.
The following code doesnt take care of exceptions that may occur due to invalid input and other things.
------------------------------------------------------------------------
#include <iostream>
#include <string.h>
using namespace std;
int indexoflargest4digitnumber(char *number);
int main(){
char number[32];
cout<<"Enter number:";
cin>>number;
int maxIndex = indexoflargest4digitnumber(number);
cout.write(number+maxIndex, 4);
return 0;
}
int indexoflargest4digitnumber(char *number) {
if(number == 0)
return -1;
int result = 0;
int length = strlen(number);
int count = 0;
while ( count <= length-4 ) { //9164916500
if( number[result] < number[count] )
result = count;
else if ( number[result] == number[count]){
if( (number[result+1] <= number[count+1]) &&
(number[result+2] <= number[count+2]) &&
(number[result+3] < number[count+3]))
result = count;
}
count++;
}
return result;
}
What should be the output of 9164916500, in this case it will be 9165 but above application will yield 9164 which I think not correct.
I have one more Doubt.. you are getting the input from command prompt that mean it's string. If it's a numaric variable, suppose getting output from some other function then it will not work.
The code returns 9164 instead of 9165 in case of "9165916489". Guess the || operators should be replaced by &&
@suma:
yes A && B && C is supposed to be executed from L->R so && was needed. I have corrected it now. Thanks
Also, regarding and string Vs numeric case, I will say (1) We can always convert number to string. (2) more importantly, If we dont convert to string and treat it as integer, think how many times we will have to do / and %.
The following program works fine with all kind of inputs.
#include<stdio.h>
void main()
{
int i, j, k, m = 9;
int a[10], b[4] = {0, 0, 0, 0}, sum1 = 0, f_sum = 0;
printf("\nEnter the 10 digit number whose starting digit is greater 0\n");
for(i = 0; i < 10; i++)
scanf("%d", &a[i]);
//---------ACTUAL LOGIC------------//
while(m >= 0)
{
for(k = 0; k < 7; k++)
{
if(a[k] == m)
{
sum1 = a[k] * 1000 + a[k+1] * 100 + a[k+2] * 10 + a[k+3];
if(sum1 > f_sum)
{
f_sum = sum1;
for(i = 0, j = k; i < 4; i++, j++)
{
b[i] = a[j];
}
}
}
}
--m;
}
printf("\nThe greatest number in the entered number is:\n");
for(i = 0; i < 4; i++)
printf("%d", b[i]);
}
A better way of doing it would be to get the indices of the greatest number in the array for 0 to n-4-1 (in this case 0 to 5).
If you get just one instance of that number, i,i+1,i+2,i+3 would be you largest continuous 4- digit number.
If you have two indices, a and b, check for a+1 and b+1, which is greater, and goes on.
This way the average time complexity of the problem improves dramatically comparedd to the above solution.
int getMax4DigitContNum (string num) {
int max = 0, temp = 0;
// Forward
for (int i = num.length() - 4; i < num.length(); ++i) {
if (i < 0) {
continue;
}
temp = temp * 10 + num.at(i) - '0';
}
temp = max;
for (int i = num.length() - 5; i >= 0; --i) {
temp = temp / 10 + (num.at(i) - '0') * 1000;
if (temp > max) {
max = temp;
}
}
// Reverse
temp = 0
for (int i = 3; i >= 0; --i) {
if (i >= num.length()) {
continue;
}
temp = temp * 10 + num.at(i) - '0';
}
if (temp > max) {
max = temp;
}
for (int i = 4; i < num.length(); ++i) {
temp = temp / 10 + (num.at(i) - '0') * 1000;
if (temp > max) {
max = temp;
}
}
return max;
}
#include<stdio.h>
void main()
{
int i, j, k, m = 9;
int a[10], b[4] = {0, 0, 0, 0};
printf("\nEnter the 10 digit number whose starting digit is greater 0\n");
for(i = 0; i < 10; i++)
scanf("%d", &a[i]);
//---------ACTUAL LOGIC------------//
while(m >= 0)
{
for(k = 0; k < 7; k++)
{
if(a[k] == m)
{
for(i = 0, j = k; i < 4; i++, j++)
{
if(a[j] < b[i])
break;
else
b[i] = a[j];
}
}
}
--m;
}
printf("\nThe greatest number in the entered number is:\n");
for(i = 0; i < 4; i++)
printf("%d", b[i]);
}
private static int findBiggest(int n) {
int big = 0;
String temp = "" + n;
for (int i = 0; i <= (temp.length() - 4); i++) {
int buf = Integer.parseInt(temp.substring(i, (i + 4)));
if (big <= buf) {
big = buf;
}
}
return big;
}
Below is the full length class implementation.
public class Main {
public static void main(String argc[]) {
int n = 1234567891;
int big = findBiggest(n);
System.out.println("big is : " + big);
}
private static int findBiggest(int n) {
int big = 0;
String temp = "" + n;
for (int i = 0; i <= (temp.length() - 4); i++) {
int buf = Integer.parseInt(temp.substring(i, (i + 4)));
if (big <= buf) {
big = buf;
}
}
return big;
}
}
AnanthaNag KUNDANALA
#include <iostream>
#include <cstring>
int findTheMAX4SubSet(char* num);
int main (int argc, char * const argv[]) {
// insert code here...
char number[32];
std::cout << "Enter the number";
std::cin >> number;
int maxIndex = findTheMAX4SubSet(number);
std::cout.write(number+maxIndex, 4);
return 0;
}
int findTheMAX4SubSet(char* num){
int result = 0;
int subLengthOfString = 4;
int index = 0;
int subsetMaxSum = 0;
if (num == 0) {
result = -1;
}
int lengthOfString = strlen(num);
//std::cout << lengthOfString << std::endl;
while (index <= (lengthOfString - subLengthOfString)) {
int tempSum = num[index] + num[index + 1] + num[index+2] +num[index+3];
if (tempSum > subsetMaxSum ) {
subsetMaxSum = tempSum;
result = index;
}
index++;
}
return result;
}
what if the given number is really big?
in that case you cant use an int to store the num
better to assume num is represented by string
k is number of continuous digits needed
void findgreat(char* str, int k)
{
short len = strlen(str);
char buf[5] = { 0, };
char* begin = str;
char* end = str + len - 4;
char* index = NULL;
char max = *begin;
index = begin;
begin++;
while (begin != end)
{
if (*begin < max)
{
begin++;
}
else if (*begin == max)
{
if (strncmp(begin, index, k) > 0)
{
max = *begin;
index = begin;
begin++;
}
else
begin++;
}
else
{
max = *begin;
index = begin;
begin++;
}
}
for (short i = 0; i < 4; i++)
cout << index[i] << " ";
}
what if the number is really big like 100 digits
then we cant use int
here k is number of continuous digits
void findgreat(char* str, int k)
{
short len = strlen(str);
char buf[5] = { 0, };
char* begin = str;
char* end = str + len - 4;
char* index = NULL;
char max = *begin;
index = begin;
begin++;
while (begin != end)
{
if (*begin < max)
{
begin++;
}
else if (*begin == max)
{
if (strncmp(begin, index, k) > 0)
{
max = *begin;
index = begin;
begin++;
}
else
begin++;
}
else
{
max = *begin;
index = begin;
begin++;
}
}
for (short i = 0; i < 4; i++)
cout << index[i] << " ";
}
#include<iostream>
using namespace std;
int main()
{
char x[10];
int y[10],sum=0,n,a,b;
cout<<"enter the 10 digit no.\n";
cin>>x;
for(a=0;a<10;a++)
y[a]=x[a]-'0';
n=y[0]*1000+y[1]*100+y[2]*10+y[3];
b=4;
sum=n;
for(;b<10;b++)
{
sum=(sum%1000)*10+y[b];
if(sum>n)n=sum;
}
cout<<n<<endl;
}
@mystry
I have stated above in the question itself that it shoud be continuous. That means you are not supposed to traverse back n forth, only forward traversal.
#include <iostream>
using namespace std;
main(int argc, char* argv[])
{
// char num[]="9164352435";
char num[]="9164916500";
int i=0,k=0;
//split the number with 4 char
int size=sizeof(num);
char** split_char;
split_char=new char*[size];
for( int k=0;k < size-4 ;k++)
split_char[k]=new char[5];
for( k=0;k < size-4 ;k++){
strncpy(split_char[k],num+i,4);
i++;
}
int max=atol(split_char[0]);
for( int j=1;j<k;j++)
if( max < atoi(split_char[j]))
max =atoi(split_char[j]);
cout<< "Max:"<< max << endl;
}
Solution :
#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;
vector<int> vecInt;
vector<int> vecGrpFourInt;
int multiple=1000;
int num=0;
void getFour(vector<int> vec)
{
//count combinations of four's
int size=0;
for(vector<int>::iterator it=vecInt.begin();it!=vecInt.end();it++)
{
//count to stop once 4 numbers picked
int count=0;
while(count<4)
{
//check if it is at 6th positon then once it is at 7th we should not proceed
if(vecInt.size()>=(size+4))
{
//create the number
num=num+multiple*(*it);
multiple=multiple/10;
++it;
++count;
}
else
{
count=4;
break;
}
}
//add the number created in separate vector so that we can use this in end after sorting to get max num
if(num>999)
{
vecGrpFourInt.push_back(num);
num=0;
multiple=1000;
}
// get back iterator 'it' to position it was at the begining of loop
if(vecInt.size()>=(size+4))
{
while(count>0)
{
--it;
--count;
}
}
++size;
}
vecGrpFourInt.resize(size);
}
int main()
{
//9164352435
vecInt.push_back(9);vecInt.push_back(1);vecInt.push_back(6);vecInt.push_back(4);vecInt.push_back(3);vecInt.push_back(5);vecInt.push_back(2);vecInt.push_back(4);vecInt.push_back(3);vecInt.push_back(5);
vecInt.resize(10);
getFour(vecInt);
sort (vecGrpFourInt.begin(), vecGrpFourInt.end());
int max=(vecGrpFourInt.back());
cout<<"greatest:"<<max<<endl;
vecInt.clear();
vecGrpFourInt.clear();
//9164916500
vecInt.push_back(9);vecInt.push_back(1);vecInt.push_back(6);vecInt.push_back(4);vecInt.push_back(9);vecInt.push_back(1);vecInt.push_back(6);vecInt.push_back(5);vecInt.push_back(0);vecInt.push_back(0);
vecInt.resize(10);
getFour(vecInt);
sort (vecGrpFourInt.begin(), vecGrpFourInt.end());
int max2=(vecGrpFourInt.back());
cout<<"greatest:"<<max2<<endl;
getchar();
return 0;
}
Here is my solution, works in O(n)
- Ramayan Tiwari January 24, 2012#include <iostream> using namespace std; int FindGreatest(int num); int main(void) { int number = 1298349923; cout<<FindGreatest(number)<<endl; return 0 ; } int FindGreatest(int num) { int max = -1; while(num>1000) { long rem = num%10000; if(rem > max) max = rem; num /=10; } return max; }