koosha.nejad
BAN USERYes it does, it'll give you "cacbc"
- koosha.nejad November 11, 2015Are we allowed to modify the original matrix?
- koosha.nejad November 10, 2015Here's the code with indentations
bool IsReversible( int n )
{
int reverse = 0;
int n_copy = n;
while ( n > 0 )
{
reverse *= 10;
switch ( n%10 )
{
case 0:
reverse += 0;
break;
case 1:
reverse += 1;
break;
case 6:
reverse += 9;
break;
case 8:
reverse += 8;
break;
case 9:
reverse += 6;
break;
default:
return false;
}
n /= 10;
}
return ( n_copy == reverse );
}
build up the reverse number as follows:
-replace 0 with 0
-replace 1 with 1
-replace 6 with 9
-replace 8 with 8
-replace 9 with 6
For all other digits, return FALSE
At the end if the reverse number is equal to the original number return true; otherwise return false
here's the code:
bool IsReversible( int n )
{
int reverse = 0;
int n_copy = n;
while ( n > 0 )
{
reverse *= 10;
switch ( n%10 )
{
case 0:
reverse += 0;
break;
case 1:
reverse += 1;
break;
case 6:
reverse += 9;
break;
case 8:
reverse += 8;
break;
case 9:
reverse += 6;
break;
default:
return false;
}
n /= 10;
}
return ( n_copy == reverse );
}
Here's the sample output:
69 is reversible
916 is reversible
123 is not reversible
6009 is reversible
6119 is reversible
8698 is reversible
8668 is not reversible
66899 is reversible
I don't think we can do better than O(n^2), but we can do some optimizations as follows:
1: The first loop starts at zero, indicating the start of the string; but we do not need to go all the way to end; once we find a legal string with length K, then we know the start must be at least (K-1) indices before the end of the string
2: For the second loop, indicating the end of the string, start from the end and go backward, two notes here
2.1: once you find a legal word, you can break from the loop
2.2: you don't need to go all the way back to "i",
Here's the code
bool IsLegalWork( const char * s, int start, int end );
void FindLongestLegal( const char * s )
{
int n = strlen(s);
int i,j;
int LegalStart = 0;
int LegalLength = 0;
for ( i = 0 ; i < n - LegalLength ; i++ )
{
for ( j = n-1 ; j > i + LegalLength ; j-- )
{
if ( LegalWord( s, i , j ) )
{
if ( LegalLength < j - i + 1 )
{
LegalStart = i;
LegalLength = j - i + 1;
}
break;
}
}
}
}
The way I see it, T="aab" is same as T="ab", don't you agree?
- koosha.nejad November 05, 2015here's a simple solution in O(n*log(n))
sort()
i = 0;
j = ArraySize - 1
while ( i<j)
{
if ( -A[i] > A[j] ) i++
else if ( -A[i] < A[j] ) j++
else You have found a pair, i++, j++
}
Actually I believe it's O(n^2),
consider {(1,2),(2,3),....,(n,n+1)} with range (1,n)
What's the time complexity? it's kinda hard to follow your code, could you please explain?
- koosha.nejad November 03, 2015I'm afraid you didn't understand the question, I don't think O(n) is possible
- koosha.nejad November 03, 2015Could you please elaborate?
- koosha.nejad November 03, 2015I have a solution that is O(n*log(n*k)), k:number of elements in the prime set
-First insert "1" to the set
-in each iteration, get the ith element of the set ( i is the iterator ) and multiply it by each element in the prime set and add it to the set
-perform n iteration
Time Complexity: we are adding at most k elements in each iterations, so the size of the set is less than or equal to (n*k), and we have n iterations, so it can be done in O(n*log(n*k)), order O(n*log(n)) is also achievable, but it's a bit complcated
c++ Code:
int getNthNumber(vector<int>& primes, int n)
{
set<int> nums;
set<int>::iterator it;
nums.insert( 1 );
// PRINTING--------------------------------------------------------
std::vector<int>::iterator iter;
std::set<int>::iterator iter2;
std::cout << "INPUT:{";
for ( iter = primes.begin() ; iter != primes.end() ; ++iter )
{
std::cout << *iter << ", ";
}
std::cout << "} N = " << n <<"\n\n";
//-----------------------------------------------------------------
//Now we start from the beginning of the set, every time we see a number
//We multiply it by every element in the original prime set and add it to our set
int new_number;
iter2 = nums.begin();
int counter = 1;
while (1)
{
if ( counter == n )
{
break;
}
std::cout << "Iteration " << counter++ << ", Current number is "<< (*iter2) << "\n" ;
for ( iter = primes.begin() ; iter != primes.end() ; ++iter )
{
new_number = (*iter)*(*iter2);
std::cout << " Adding number " << new_number << "\n" ;
nums.insert( new_number );
}
++iter2;
}
std::cout << "\nPrinting the result\n";
std::cout << nums.size() << " numbers in the set\n";
counter = 0;
for ( iter2 = nums.begin() ; counter < n ; ++iter2 )
{
std::cout << ++counter << ": " << (*iter2) << "\n";
}
return 0;
}
Sample Output:
INPUT:{2, 5, 7, 11, } N = 10
Iteration 1, Current number is 1
Adding number 2
Adding number 5
Adding number 7
Adding number 11
Iteration 2, Current number is 2
Adding number 4
Adding number 10
Adding number 14
Adding number 22
Iteration 3, Current number is 4
Adding number 8
Adding number 20
Adding number 28
Adding number 44
Iteration 4, Current number is 5
Adding number 10
Adding number 25
Adding number 35
Adding number 55
Iteration 5, Current number is 7
Adding number 14
Adding number 35
Adding number 49
Adding number 77
Iteration 6, Current number is 8
Adding number 16
Adding number 40
Adding number 56
Adding number 88
Iteration 7, Current number is 10
Adding number 20
Adding number 50
Adding number 70
Adding number 110
Iteration 8, Current number is 11
Adding number 22
Adding number 55
Adding number 77
Adding number 121
Iteration 9, Current number is 14
Adding number 28
Adding number 70
Adding number 98
Adding number 154
Printing the result
28 numbers in the set
1: 1
2: 2
3: 4
4: 5
5: 7
6: 8
7: 10
8: 11
9: 14
10: 16
could you please elaborate? you have a min-heap and a queue?
- koosha.nejad November 02, 2015Please note that my code is basically a MERGE SORT and I just added ONE line of code:
input->at(i).value += ( end - j + 1 );
Merge sort with tweak will do it;
Assume we have the following numbers, for each number we also define a "value" which is the number of items greater than me with a bigger index, this value is initialized to zero
16, 17, 9, 0, 19, 24, 3, 8,
Now I explain the last step of the merge sort, here's what I have
{number=0 value=0 },{number=9 value=0 },{number=16 value=1 },{number=17 value=0 }
{number=3 value=1 },{number=8 value=0 },{number=19 value=1 },{number=24 value=0 }
- Pick "0": 0 is less than 3, so it's less than 4 elements in the second half, so it's value is insreased by 4
- Pick "3": it's from the second half, do nothing
- Pick "8": it's from the second half, do nothing
- Pick "9": 9 is smallet than 2 elements in the second half, so it's value is insreased by 2
- Pick "16": 16 is smallet than 2 elements in the second half, so it's value is insreased by 2
- Pick "17": 17 is smallet than 2 elements in the second half, so it's value is insreased by 2
- Pick "19": it's from the second half, do nothing
- Pick "24": it's from the second half, do nothing
Here is the final result
(0 , 4)
(3 , 1)
(8 , 0)
(9 , 2)
(16 , 3)
(17 , 2)
(19 , 1)
(24 , 0)
Here's the code
struct number_t
{
int number;
int value;
};
std::vector<number_t> temp_array;
void MergeSort( std::vector<number_t>* input, int start, int end )
{
if ( start == end )
{
return;
}
int middle = floor((double)(start+end)/2);
MergeSort( input, start, middle );
MergeSort( input, middle+1, end );
temp_array.clear();
int i = start;
int j = middle+1;
while ( ( i <= middle ) && ( j <= end ) )
{
if ( input->at(i).number < input->at(j).number )
{
input->at(i).value += ( end - j + 1 ); // this is MAGIC line added to merge sort
temp_array.push_back( input->at(i) );
i++;
}
else
{
temp_array.push_back( input->at(j) );
j++;
}
}
//copying the rest
while ( i <= middle )
{
temp_array.push_back( input->at(i) );
i++;
}
while ( j <= end )
{
temp_array.push_back( input->at(j) );
j++;
}
//Now copy on the input array
for ( i = start ; i <= end ; i++ )
{
input->at(i) = temp_array[ i - start];
}
}
The number of permutations is equal to the length of the array to the power of n, in our example it's 3^2 = 9;
Then we loop from 0 to the number of permutations calculated above, and treat each iteration as a number with base n,
void Permutations( std::vector<int>* input, int n )
{
int j;
int index;
int number;
size_t length = input->size();
int total_permutations = pow( (double)length, (double)n );
for ( int i = 0 ; i < total_permutations ; i++ )
{
number = i;
for ( j = 0 ; j < n ; j++ )
{
index = number%length;
std::cout << input->at(index) << ", ";
number /= length;
}
std::cout << "\n";
}
}
here is the output when n = 2
2, 2,
3, 2,
4, 2,
2, 3,
3, 3,
4, 3,
2, 4,
3, 4,
4, 4,
here is the output when n = 3
2, 2, 2,
3, 2, 2,
4, 2, 2,
2, 3, 2,
3, 3, 2,
4, 3, 2,
2, 4, 2,
3, 4, 2,
4, 4, 2,
2, 2, 3,
3, 2, 3,
4, 2, 3,
2, 3, 3,
3, 3, 3,
4, 3, 3,
2, 4, 3,
3, 4, 3,
4, 4, 3,
2, 2, 4,
3, 2, 4,
4, 2, 4,
2, 3, 4,
3, 3, 4,
4, 3, 4,
2, 4, 4,
3, 4, 4,
4, 4, 4,
Can be done on O(n*log(n))
- koosha.nejad October 22, 2015No matter what you use, I strongly believe O(n) time is not possible
- koosha.nejad October 16, 2015Simple, Correct, and Beautiful
- koosha.nejad October 16, 2015You are using a HUGE array, it specifically states that this is not acceptable
- koosha.nejad October 16, 2015and samples:
-----------------------
Original Array: 0, 5, 3, 6,
Missing Numbers: 1, 2, 4, 7,
-----------------------
Original Array: 3, 12, 8, 13, 11, 9, 0,
Missing Numbers: 1, 2, 4, 5, 6, 7, 10,
-----------------------
Original Array: 2, 0, 4,
Missing Numbers: 1, 3, 5,
-----------------------
Original Array: 8, 9, 13, 5, 0, 11, 3,
Missing Numbers: 1, 2, 4, 6, 7, 10, 12,
-----------------------
Original Array: 2, 3, 4,
Missing Numbers: 0, 1, 5,
-----------------------
Original Array: 4, 7, 5, 6,
Missing Numbers: 0, 1, 2, 3,
-----------------------
Original Array: 0, 5, 4,
Missing Numbers: 1, 2, 3,
-----------------------
Original Array: 3, 2, 4, 5,
Missing Numbers: 0, 1, 6, 7,
-----------------------
Original Array: 4, 1, 7, 2,
Missing Numbers: 0, 3, 5, 6,
-----------------------
Original Array: 7, 11, 6, 4, 9, 8,
Missing Numbers: 0, 1, 2, 3, 5, 10,
-----------------------
Original Array: 0, 11, 9, 2, 4, 7,
Missing Numbers: 1, 3, 5, 6, 8, 10,
-----------------------
Original Array: 4, 6, 2, 0, 3,
Missing Numbers: 1, 5, 7, 8, 9,
-----------------------
Original Array: 4, 0, 5,
Missing Numbers: 1, 2, 3,
-----------------------
Original Array: 0, 7, 6, 5,
Missing Numbers: 1, 2, 3, 4,
-----------------------
Original Array: 3, 2, 6, 5, 9,
Missing Numbers: 0, 1, 4, 7, 8,
-----------------------
Original Array: 0, 6, 7, 8, 9,
Missing Numbers: 1, 2, 3, 4, 5,
-----------------------
Original Array: 8, 13, 5, 3, 7, 11, 9,
Missing Numbers: 0, 1, 2, 4, 6, 10, 12,
-----------------------
Original Array: 6, 7, 5, 4, 3,
Missing Numbers: 0, 1, 2, 8, 9,
-----------------------
Original Array: 8, 1, 0, 4, 2,
Missing Numbers: 3, 5, 6, 7, 9,
-----------------------
Original Array: 8, 9, 5, 10, 0, 7,
Missing Numbers: 1, 2, 3, 4, 6, 11,
-----------------------
Original Array: 0, 5, 2, 3,
Missing Numbers: 1, 4, 6, 7,
-----------------------
Original Array: 1, 0, 2,
Missing Numbers: 3, 4, 5,
-----------------------
Original Array: 7, 5, 10, 6, 3, 2,
Missing Numbers: 0, 1, 4, 8, 9, 11,
-----------------------
Original Array: 2, 5, 6, 4, 3,
Missing Numbers: 0, 1, 7, 8, 9,
-----------------------
Original Array: 4, 6, 1, 2, 9, 11,
Missing Numbers: 0, 3, 5, 7, 8, 10,
-----------------------
Original Array: 7, 0, 6, 1,
Missing Numbers: 2, 3, 4, 5,
-----------------------
Original Array: 3, 4, 5,
Missing Numbers: 0, 1, 2,
-----------------------
Original Array: 6, 8, 5, 4, 2,
Missing Numbers: 0, 1, 3, 7, 9,
-----------------------
Original Array: 0, 8, 7, 6, 4,
Missing Numbers: 1, 2, 3, 5, 9,
-----------------------
Original Array: 3, 2, 1,
Missing Numbers: 0, 4, 5,
-----------------------
Original Array: 11, 12, 3, 2, 13, 1, 7,
Missing Numbers: 0, 4, 5, 6, 8, 9, 10,
-----------------------
Original Array: 1, 7, 4, 5, 8,
Missing Numbers: 0, 2, 3, 6, 9,
-----------------------
Original Array: 6, 4, 5, 7,
Missing Numbers: 0, 1, 2, 3,
-----------------------
Original Array: 4, 0, 2,
Missing Numbers: 1, 3, 5,
-----------------------
Original Array: 2, 0, 4,
Missing Numbers: 1, 3, 5,
-----------------------
Original Array: 3, 12, 6, 9, 11, 8, 0,
Missing Numbers: 1, 2, 4, 5, 7, 10, 13,
-----------------------
Original Array: 0, 4, 5,
Missing Numbers: 1, 2, 3,
-----------------------
Original Array: 1, 11, 2, 3, 10, 0,
Missing Numbers: 4, 5, 6, 7, 8, 9,
-----------------------
Original Array: 9, 8, 7, 4, 5, 6,
Missing Numbers: 0, 1, 2, 3, 10, 11,
-----------------------
Original Array: 3, 4, 1, 2,
Missing Numbers: 0, 5, 6, 7,
-----------------------
Original Array: 0, 5, 1,
Missing Numbers: 2, 3, 4,
-----------------------
Original Array: 4, 5, 2, 3,
Missing Numbers: 0, 1, 6, 7,
-----------------------
Original Array: 4, 2, 3,
Missing Numbers: 0, 1, 5,
-----------------------
Original Array: 10, 8, 7, 9, 6, 11,
Missing Numbers: 0, 1, 2, 3, 4, 5,
-----------------------
Original Array: 3, 5, 4,
Missing Numbers: 0, 1, 2,
-----------------------
Original Array: 3, 12, 11, 9, 0, 8, 13,
Missing Numbers: 1, 2, 4, 5, 6, 7, 10,
-----------------------
Original Array: 2, 1, 7, 4,
Missing Numbers: 0, 3, 5, 6,
-----------------------
Original Array: 10, 1, 7, 6, 2, 12, 4,
Missing Numbers: 0, 3, 5, 8, 9, 11, 13,
-----------------------
Original Array: 4, 0, 5, 7, 8, 9,
Missing Numbers: 1, 2, 3, 6, 10, 11,
-----------------------
Original Array: 13, 1, 11, 9, 10, 7, 5,
Missing Numbers: 0, 2, 3, 4, 6, 8, 12,
-----------------------
Original Array: 4, 5, 3,
Missing Numbers: 0, 1, 2,
-----------------------
Original Array: 7, 8, 6, 3, 10, 11,
Missing Numbers: 0, 1, 2, 4, 5, 9,
-----------------------
Original Array: 1, 3, 6, 10, 8, 11,
Missing Numbers: 0, 2, 4, 5, 7, 9,
-----------------------
Original Array: 1, 0, 11, 2, 4, 9,
Missing Numbers: 3, 5, 6, 7, 8, 10,
-----------------------
Original Array: 6, 7, 0, 1,
Missing Numbers: 2, 3, 4, 5,
-----------------------
Original Array: 1, 0, 2, 3,
Missing Numbers: 4, 5, 6, 7,
-----------------------
Original Array: 2, 8, 5, 6, 3, 11, 7,
Missing Numbers: 0, 1, 4, 9, 10, 12, 13,
-----------------------
Original Array: 9, 13, 5, 7, 1, 3, 11,
Missing Numbers: 0, 2, 4, 6, 8, 10, 12,
-----------------------
Original Array: 7, 8, 0, 6, 9,
Missing Numbers: 1, 2, 3, 4, 5,
-----------------------
Original Array: 6, 4, 7, 2, 3, 11,
Missing Numbers: 0, 1, 5, 8, 9, 10,
-----------------------
Original Array: 0, 4, 5,
Missing Numbers: 1, 2, 3,
-----------------------
Original Array: 1, 9, 10, 5, 0, 2,
Missing Numbers: 3, 4, 6, 7, 8, 11,
-----------------------
Original Array: 6, 5, 7, 3, 4,
Missing Numbers: 0, 1, 2, 8, 9,
-----------------------
Original Array: 5, 4, 6, 1, 2, 3, 7,
Missing Numbers: 0, 8, 9, 10, 11, 12, 13,
-----------------------
Original Array: 8, 2, 5, 4, 1,
Missing Numbers: 0, 3, 6, 7, 9,
-----------------------
Original Array: 6, 8, 7, 2, 5, 3, 4,
Missing Numbers: 0, 1, 9, 10, 11, 12, 13,
-----------------------
Original Array: 4, 3, 2, 5,
Missing Numbers: 0, 1, 6, 7,
-----------------------
Original Array: 7, 4, 6, 0, 8,
Missing Numbers: 1, 2, 3, 5, 9,
-----------------------
Original Array: 5, 3, 4,
Missing Numbers: 0, 1, 2,
-----------------------
Original Array: 1, 6, 0, 3,
Missing Numbers: 2, 4, 5, 7,
-----------------------
Original Array: 5, 0, 1,
Missing Numbers: 2, 3, 4,
-----------------------
Original Array: 5, 1, 3,
Missing Numbers: 0, 2, 4,
-----------------------
Original Array: 9, 7, 3, 5, 1,
Missing Numbers: 0, 2, 4, 6, 8,
-----------------------
Original Array: 3, 0, 2, 1,
Missing Numbers: 4, 5, 6, 7,
-----------------------
Original Array: 12, 2, 1, 11, 13, 10, 0,
Missing Numbers: 3, 4, 5, 6, 7, 8, 9,
-----------------------
Original Array: 4, 5, 3,
Missing Numbers: 0, 1, 2,
-----------------------
Original Array: 4, 6, 2, 1, 10, 5, 7,
Missing Numbers: 0, 3, 8, 9, 11, 12, 13,
-----------------------
Original Array: 4, 3, 2,
Missing Numbers: 0, 1, 5,
-----------------------
Original Array: 0, 13, 1, 12, 10, 11, 2,
Missing Numbers: 3, 4, 5, 6, 7, 8, 9,
-----------------------
Original Array: 3, 6, 5, 7, 2, 10,
Missing Numbers: 0, 1, 4, 8, 9, 11,
-----------------------
Original Array: 4, 0, 2,
Missing Numbers: 1, 3, 5,
-----------------------
Original Array: 12, 2, 6, 7, 1, 11, 10,
Missing Numbers: 0, 3, 4, 5, 8, 9, 13,
-----------------------
Original Array: 0, 4, 2, 5, 7, 3,
Missing Numbers: 1, 6, 8, 9, 10, 11,
-----------------------
Original Array: 3, 2, 1, 9, 0,
Missing Numbers: 4, 5, 6, 7, 8,
-----------------------
Original Array: 1, 5, 3, 8, 6, 10,
Missing Numbers: 0, 2, 4, 7, 9, 11,
-----------------------
Original Array: 0, 2, 1,
Missing Numbers: 3, 4, 5,
-----------------------
Original Array: 0, 5, 1,
Missing Numbers: 2, 3, 4,
-----------------------
Original Array: 8, 7, 9, 5, 6,
Missing Numbers: 0, 1, 2, 3, 4,
-----------------------
Original Array: 3, 7, 6, 8, 10, 5,
Missing Numbers: 0, 1, 2, 4, 9, 11,
-----------------------
Original Array: 8, 7, 10, 2, 6, 11, 5,
Missing Numbers: 0, 1, 3, 4, 9, 12, 13,
-----------------------
Original Array: 4, 8, 0, 5, 7, 3,
Missing Numbers: 1, 2, 6, 9, 10, 11,
-----------------------
Original Array: 0, 7, 6, 4, 8,
Missing Numbers: 1, 2, 3, 5, 9,
-----------------------
Original Array: 5, 1, 0,
Missing Numbers: 2, 3, 4,
-----------------------
Original Array: 10, 6, 2, 3, 11, 1,
Missing Numbers: 0, 4, 5, 7, 8, 9,
-----------------------
Original Array: 8, 13, 9, 3, 0, 4, 12,
Missing Numbers: 1, 2, 5, 6, 7, 10, 11,
-----------------------
Original Array: 0, 9, 1, 4, 10, 6, 12,
Missing Numbers: 2, 3, 5, 7, 8, 11, 13,
-----------------------
Original Array: 7, 5, 0, 2,
Missing Numbers: 1, 3, 4, 6,
-----------------------
Original Array: 4, 5, 3,
Missing Numbers: 0, 1, 2,
-----------------------
Original Array: 2, 1, 5, 4, 0, 9,
Missing Numbers: 3, 6, 7, 8, 10, 11,
-----------------------
Original Array: 0, 6, 9, 2, 8,
Missing Numbers: 1, 3, 4, 5, 7,
here's the code
#include "stdafx.h"
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include<conio.h>
using namespace std;
int MissingNumbers( std::vector<int> * original_p, std::vector<int> * missing_p )
{
size_t n = original_p->size();
int current;
int temp;
size_t i;
for ( i = 0 ; i < n ; i++ )
{
current = original_p->at(i);
while ( 1 )
{
if ( ( current < n ) && ( original_p->at(current)!=current ) )
{
temp = original_p->at(current);
original_p->at(current) = current;
current = temp;
}
else
{
break;
}
}
if ( current >= n )
{
original_p->at(i) = current;
}
}
for ( i = 0 ; i < n ; i++ )
{
if ( original_p->at(i)!=i )
{
missing_p->push_back( i );
}
}
for ( i = 0 ; i < n ; i++ )
{
current = original_p->at(i);
while ( 1 )
{
if ( ( current >= n ) && ( original_p->at(current-n)!=current ) )
{
temp = original_p->at(current-n);
original_p->at(current-n) = current;
current = temp;
}
else
{
break;
}
}
if ( current < n )
{
original_p->at(i) = current;
}
}
for ( i = 0 ; i < n ; i++ )
{
if ( original_p->at(i)!=i+n )
{
missing_p->push_back( i+n );
}
}
return 0;
}
int _tmain(int argc, _TCHAR* argv[])
{
std::vector<int> Original;
std::vector<int> Missing;
int i,j,k,temp;
int x,y;
int array_size;
for ( i = 0 ; i < 100 ; i++ )
{
Original.clear();
Missing.clear();
array_size = rand()%5 + 3;
for ( j = 0 ; j < array_size ; j++ )
{
if ( rand()%2 )
{
Original.push_back(j);
}
else
{
Original.push_back(j+array_size);
}
}
//scramble
for ( k = 0 ; k < 100 ; k++ )
{
x = rand()%array_size;
y = rand()%array_size;
temp = Original[x];
Original[x] = Original[y];
Original[y] = temp;
}
//print original
cout << endl << "-----------------------" << endl << "Original Array: " ;
for ( j = 0 ; j < array_size ; j++ )
{
cout << Original[j] << ", ";
}
cout << endl;
MissingNumbers( &Original, &Missing );
//Print Missing
cout << "Missing Numbers: " ;
for ( j = 0 ; j < array_size ; j++ )
{
cout << Missing[j] << ", ";
}
}
getch();
return 0;
}
Here is my solution, I have tested it and it works
Step I: Find missing numbers less than n
Loop through the array( i ), if (a[i] != i && i < n) => put i in the i'th position, and do the same for the item that was in the i'th position. This second loop ends either when you have an item that is in it's correct position or you see a number greater than n.
Step 2: Find missing numbers greater than or equal to numbers
Similar approach :)
it's correct, but I believe you have to do "money /= 2" anyway;
- koosha.nejad October 14, 2015-Sort the array O(n*log(n))
-Traverse the array and make sure no letter appears more than (n/2) times O(n)
-Shift the items in the odd positions (1,3,5,..) by (n/2+1) if n is even and by (n+1)/2 if n is odd O(n)
-you are done :)
Proof of correctness:
consider any block of letters starting at position x and ending at position y;
1- Since every other element of this block is replaced by a letter of another block, there would be no duplicates in this block.
2- Elements removed from this block will be moved another blocks and they would not be adjacent
This is very similar to "qaz" problem, it can be solved using "merge sort", in each step, when merging, find out how much the length of the the first half can be increased when the second half comes in, here the c++ code; look for "updating counts", that's where the counts are updated,
#include "stdafx.h"
#include <vector>
#include <conio.h>
struct data_t
{
int value;
int old_count;
int new_count;
};
void merge(std::vector<data_t> * values, int low, int high, int mid)
{
std::vector<data_t> temp;
int i, j;
//----------------------------------------------------------------------------------------
//updating counts
for ( i = mid ; i >= low ; i-- )
{
values->at(i).new_count = 0;
}
i = low;
j = mid + 1;
int junk;
while (i <= mid && j <= high)
{
if ( values->at(i).value < values->at(j).value)
{
i++;
}
else
{
if ( ( j == high ) || ( values->at(j).value != values->at(j+1).value ) )
if ( i > low )
if ( values->at(i).value != values->at(j).value )
{
values->at(i-1).new_count++;
}
j++;
}
}
while ( (j <= high) )
{
if ( ( j == high ) || ( values->at(j).value != values->at(j+1).value ) )
if ( i > low )
if ( ( values->at(i).value != values->at(j).value ) || ( i > mid ) )
{
values->at(i-1).new_count++;
}
j++;
}
int total = 0;
for ( i = mid ; i >= low ; i-- )
{
total += values->at(i).new_count;
values->at(i).old_count += total;
}
//-------------------------------------------------------------------------------------
//Merging
i = low;
j = mid + 1;
while (i <= mid && j <= high)
{
if ( values->at(i).value < values->at(j).value)
{
temp.push_back( values->at(i) );
i++;
}
else
{
temp.push_back( values->at(j) );
j++;
}
}
while (i <= mid)
{
temp.push_back( values->at(i) );
i++;
}
while (j <= high)
{
temp.push_back( values->at(j) );
j++;
}
for (i = low; i <= high; i++)
{
values->at(i) = temp[ i - low];
}
}
void mergesort(std::vector<data_t> * values, int low, int high)
{
int mid;
if (low < high)
{
mid=(low+high)/2;
mergesort(values,low,mid);
mergesort(values,mid+1,high);
merge(values,low,high,mid);
}
return;
}
int _tmain(int argc, _TCHAR* argv[])
{
std::vector<data_t> values;
data_t data;
data.old_count = 0;
data.new_count = 0;
data.value = -1; values.push_back( data );
data.value = 2; values.push_back( data );
data.value = 100; values.push_back( data );
data.value = 100; values.push_back( data );
data.value = 100; values.push_back( data );
data.value = 100; values.push_back( data );
data.value = 100; values.push_back( data );
data.value = 100; values.push_back( data );
data.value = 100; values.push_back( data );
data.value = 101; values.push_back( data );
data.value = 3; values.push_back( data );
data.value = 4; values.push_back( data );
data.value = 5; values.push_back( data );
data.value = -7; values.push_back( data );
for ( size_t i = 0 ; i < values.size() ; i++ )
{
printf("%d ", values[i].value );
}
printf("\n");
mergesort( &values, 0, values.size() - 1 );
for ( size_t i = 0 ; i < values.size() ; i++ )
{
printf("%d(%d) ", values[i].value, values[i].old_count+1 );
}
printf("\n");
getch();
return 0;
}
doesn't work, if I am sending 1, 15 or 15,1, you are sending the same thing;
- koosha.nejad February 23, 2015smart solution, I believe you should have used "bits += ceil(log((double)x));
if I need 2.5 bits for sth and 2.5 bits for the next, then I will need 6 bits total, not 5
smart solution, I believe you should have used "bits += ceil(log((double)x));
if I need 2.5 bits for sth and 2.5 bits for the next, then I will need 6 bits total, not 5
Sort the cards and a sequential index to cards, then each card has a number between 0-51 (inclusive); which can be represented by 6 bits; hence 6*52, but we can do much better;
send the first card, remove that card from the deck and update the sequence number of the cards, (i.e. remaining the cards will have numbers from 0-50)
- for the first 20 cards you need 6 bits to represent each card: 6*20
Now you have 32 cards left, and each card can be represented by 5 bits;
- for the next 16 cards, you need 5 bits to represent each card: 5*16
Now you have 16 cards left, and each card can be represented by 4 bits;
Now you need 4*8,
and then 3*4,
and then 2*2;
and then 1*1;
Total is: 6*20 + 5*16+ 4*8 + 3*4 + 2*2 + 1*1,
Note that you don't need to send the last card, after knowing the 51 cards, the 52nd card is known :)
Nice answer, I believe the time complexity is O(nlogn) because you have to find the middle node each time; The following algorithm is O(n) and it works,
Call: ConvertToBST( INT_MAX ) and it returns the BST
CNode * current = root;
CNode * ConvertToBST( int n )
{
CNode * root_p = NULL;
if ( n )
{
//Build left side tree
CNode * left = ConvertToBST( n/2 );
if ( current )
{
// Root would the current node
root_p = current;
//Assing Left Tree
root_p->m_prev = left;
//Advance Current
current = current->m_next;
//Assign Right Tree
root_p->m_next = ConvertToBST( n/2 );
}
else
{
// If there is not current, Left tree is the answer
root_p = left;
}
}
return root_p;
}
Space Complexity O(N^2/3); you can do it in O(n) with Space Complexity O(1)
- koosha.nejad February 18, 2015you are supposed to find all the instances, here you are doing it for 1729 only;
- koosha.nejad February 18, 2015Time Complexity O((n^(1/3))(n^(1/3))(n^(1/3))) = O(n)
Space Complexity: O(1)
void FindCubes( int n )
{
int i,j,k,i3,j3,k3;
int max_cube = pow( (double)n, (double)1/3 );
double cube_root;
int number;
for ( i = 1 ; i < max_cube ; i++ )
{
i3 = i*i*i;
for ( j = i+1 ; j < max_cube ; j++ )
{
j3 = j*j*j;
for ( k = i+1 ; k < max_cube ; k++ )
{
if ( k != j )
{
k3 = k*k*k;
number = i3+j3-k3;
cube_root = ceil( pow( (double)number, (double)1/3 ) );
if ( ( pow( cube_root, 3 ) == number ) && ( cube_root > k ) )
{
printf("%d = %d^3 + %d^3 = %d^3 + %d^3\n", i3+j3 , i,j,k,(int)cube_root );
}
}
}
}
}
}
1729 = 13^3 + 123^3 = 93^3 + 103^3 ??!!
13^3 + 123^3 = 1863064 ; 93^3 + 103^3 = 1897084
Could you please clarify?
c=='1' and d=='9' is acceptable, but your code doesn't allow it
- koosha.nejad February 11, 2015s[i]==1 and s[i+1]==9 is acceptable, but your code doesn't allow it
- koosha.nejad February 11, 2015I believe you should replace "if(temp < 26)" with "if(temp < 26) && (temp>=10)"
- koosha.nejad February 11, 2015int CountStrings( char * s, int n )
{
if ( n < 2 )
{
return 1;
}
int number = (s[n-1]-'0') + (s[n-2]-'0')*10;
if ( ( number >= 10 ) && ( number <= 25 ) )
{
return CountStrings( s, n-1 ) + CountStrings( s, n-2 );
}
else
{
return CountStrings( s, n-1 );
}
}
here is the c++ code
int CountStrings( char * s, int n )
{
if ( n < 2 )
{
return 1;
}
int number = (s[n-1]-'0') + (s[n-2]-'0')*10;
if ( ( number >= 10 ) && ( number <= 25 ) )
{
return CountStrings( s, n-1 ) + CountStrings( s, n-2 );
}
else
{
return CountStrings( s, n-1 );
}
}
I disagree
consider the string "11111" (5 characters), the solution is 8, 5 choose 2 is 10
1- "BBBBB"
2- "BBBL"
3- "BBLB"
4- "BLBB"
5- "LBBB"
6- "BLL"
7- "LBL"
8- "LLB"
I'm afraid the answers given are wrong,
consider the string "11111" (5 characters), here are the strings you can generate:
1- "BBBBB"
2- "BBBL"
3- "BBLB"
4- "BLBB"
5- "LBBB"
6- "BLL"
7- "LBL"
8- "LLB"
NONE OF THE ANSWERS ABOVE GENERATES THIS
@Anonymous and @saurav: I don't agree with your solution
if string = "25", you can either generate "CF" or "Z", => you suggested 3
if string = "55", you can only generate "FF",=> you suggested 2
I don't think the questions is asking for sub-strings, if you want to consider sub-strings, then you have to count the number of distinct strings,
Am I missing something here?
My program output:
+ 2 4 = 6
* 8 ( + 7 12 ) = 152
( + 7 12 ) = 19
( * * 2 ( + 9 4 ) 7 ) = 182
( + 7 ( * 8 12 ) ) = 103
( + + 7 ( * 8 12 ) ( * * 2 ( + 9 4 ) 7 ) = 285
(++ 7( * 8 12 )( **2 ( + 9 4 )7 ) = 285
First of all the format of the third string is WRONG
I found this simple recursive solution, the c++ code is quite simple to follow, this algorithm works even if the spaces are missing, let me know of if you have any questions:
#include "stdafx.h"
#include "conio.h"
int StringValue( char * str, int& pos )
{
if ( !pos )
{
printf("%s = ", str );
}
int total = 0;
int operand1, operand2;
switch ( str[ pos ] )
{
case ' ':
pos++;
total = StringValue( str , pos );
break;
case '+':
pos++;
operand1 = StringValue( str , pos );
operand2 = StringValue( str , pos );
total = operand1 + operand2;
break;
case '-':
pos++;
operand1 = StringValue( str , pos );
operand2 = StringValue( str , pos );
total = operand1 - operand2;
break;
case '*':
pos++;
operand1 = StringValue( str , pos );
operand2 = StringValue( str , pos );
total = operand1 * operand2;
break;
case '/':
pos++;
operand1 = StringValue( str , pos );
operand2 = StringValue( str , pos );
total = operand1 / operand2;
break;
case '(':
pos++;
total = StringValue( str , pos );
while ( ( str[pos] != ')' ) && ( str[pos] ) )
{
pos++;
}
pos++;
break;
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
total = str[pos] - '0';
pos++;
while ( ( str[pos] >= '0' ) && ( str[pos] <= '9' ) )
{
total = total*10 + str[pos] - '0';
pos++;
}
break;
}
return total;
}
int _tmain(int argc, _TCHAR* argv[])
{
int pos = 0;
pos = 0;
printf("%d \n", StringValue("+ 2 4", pos) );
pos = 0;
printf("%d \n", StringValue("* 8 ( + 7 12 )", pos) );
pos = 0;
printf("%d \n", StringValue("( + 7 12 )", pos) );
pos = 0;
printf("%d \n", StringValue("( * * 2 ( + 9 4 ) 7 )", pos) );
pos = 0;
printf("%d \n", StringValue("( + 7 ( * 8 12 ) )", pos) );
pos = 0;
printf("%d \n", StringValue("( + + 7 ( * 8 12 ) ( * * 2 ( + 9 4 ) 7 )", pos) );
getch();
return 0;
}
Answer given by SKOR works perfectly, we can insert pairs into an std:set which will take care of sorting, below is the c++ code:
#include "stdafx.h"
#include "stdio.h"
#include "conio.h"
#include <vector>
#include <set>
using namespace std;
struct MinMax
{
int min_val;
int max_val;
};
struct comparer
{
bool operator() ( const MinMax& a, const MinMax& b )const
{
return ( a.min_val <= b.min_val ) ? true : false ;
}
};
std::set<MinMax,comparer> myset;
int _tmain(int argc, _TCHAR* argv[])
{
MinMax min_max, new_min_max;
min_max.min_val = 4;
min_max.max_val = 8;
myset.insert( min_max );
min_max.min_val = 3;
min_max.max_val = 5;
myset.insert( min_max );
min_max.min_val = -1;
min_max.max_val = 2;
myset.insert( min_max );
min_max.min_val = 10;
min_max.max_val = 12;
myset.insert( min_max );
std::set<MinMax,comparer>::iterator iter;
min_max = *myset.begin();
for ( iter = myset.begin() ; iter != myset.end() ; ++iter )
{
new_min_max = *iter;
//check for overlap
if ( new_min_max.min_val <= min_max.max_val + 1 )
{
min_max.max_val = new_min_max.max_val;
}
else // no overlap
{
printf("(%d:%d) ", min_max.min_val, min_max.max_val );
min_max = new_min_max;
}
}
printf("(%d:%d) ", min_max.min_val, min_max.max_val );
printf("\n");
getch();
return 0;
}
Consider { 10,11,12,13,1,14,15,16,17}
QAZ(10) = 7
longest incrementing sub sequence = { 10,11,12,13 }
Here is the C++ code
#include "stdafx.h"
#include "stdio.h"
#include "conio.h"
#include <deque>
using namespace std;
#define WIDTH 6
#define HEIGHT 6
int A[WIDTH*HEIGHT]=
{
1,1,1,0,1,1,
1,1,1,0,0,1,
1,0,0,0,0,1,
1,1,1,1,1,1,
1,0,0,0,1,1,
1,1,1,1,1,1
};
bool V[WIDTH*HEIGHT]; // visited ones
void PrintArray()
{
for ( int i = 0 ; i < WIDTH*HEIGHT ; i++ )
{
if ( ! (i%WIDTH) )
{
printf("\n");
}
printf("%d ", A[i]);
}
printf("\n");
}
int _tmain(int argc, _TCHAR* argv[])
{
int i;
// mark every node and NOT visited
for ( i = 0 ; i < WIDTH*HEIGHT ; i++ )
{
V[i] = false;
}
PrintArray();
bool game_over = true;
int unvisited = -1;
int new_node;
int row, col;
deque<int> my_q;
while ( game_over )
{
unvisited = -1;
//find unvisited 0
for ( i = 0 ; i < WIDTH*HEIGHT ; i++ )
{
if ( ( !V[i] ) && ( !A[i] ) )
{
unvisited = i;
break;
}
}
if ( unvisited >= 0 )
{
my_q.clear();
V[ unvisited ] = true;
my_q.push_back( unvisited );
while ( (!my_q.empty() ) && ( game_over ) )
{
unvisited = my_q.front();
my_q.pop_front();
//find the neighbors
for ( row = unvisited/WIDTH - 1 ; row <= unvisited/WIDTH+1 && game_over; row++ )
for ( col = unvisited%WIDTH - 1 ; col <= unvisited%WIDTH+1 && game_over ; col++ )
{
//check if row and col are valid
if ( ( row >=0 ) && ( row < HEIGHT ) && ( col >=0 ) && ( col < WIDTH ) )
{
new_node = row*WIDTH + col;
// if the neighbor is not visited, then add it to the queue
if ( ( !A[ new_node] ) && ( !V[ new_node ] ) )
{
V[ new_node ] = true;
my_q.push_back( new_node );
}
}
else // if row or column is not valid, game is not over
{
game_over = false;
printf("Node (row = %d, Col = %d ) is not covered.\n", unvisited/WIDTH + 1, unvisited%WIDTH + 1 );
}
}
}
}
else
{
break;
}
}
printf("Game is %s over\n",game_over?"":"NOT");
getch();
return 0;
}
1 1 1 1 1 1
1 1 1 0 0 1
1 0 0 0 0 1
1 0 0 0 0 1
1 0 0 0 1 1
1 1 1 1 1 1
Game is over
1 1 1 1 1 1
1 1 1 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1
1 0 0 0 1 1
1 1 1 1 1 1
Game is over
1 1 1 0 1 1
1 1 1 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1
1 0 0 0 1 1
1 1 1 1 1 1
Node (row = 1, Col = 4 ) is not covered.
Game is NOT over
My bad, Uday is right, it doesn't work for "abccc", here you have indices 0,1,2,3,4 as you said it puts "a" at 0 , "b" at 2, c at 4, c at 1, and c at 3,
- koosha.nejad November 11, 2015you will get "acbcc"