James
BAN USER- 0of 0 votes
AnswersWrite code in the language of your choice to determine how many numbers between 1 and 100,000 contain an even number of odd digits
- James in United States
What I understand that number of digit in a number should be odd
is..
2 4 6 8 are even number which having only 1 digit and 1 is odd number
10 12 14 18 ……are even number but number of digit in these number are 2. 2 is not odd number hence we gonna discard all these number
102 104 106 …. Are even number and number of digit in these number is 3 that is odd number hence we will count these number
1000 1002 1004….are even number and number of digit in these number is 4 that is even number hence we will not count these number…
Please let me know if you think differently.| Report Duplicate | Flag | PURGE
Microsoft Software Developer
if I modify your code and run it for 1 to 100 I can see it gives totalnums=50
However this in not correct
What I understand that number of digit in a number should be odd
is..
2 4 6 8 are even number which having only 1 digit and 1 is odd number
10 12 14 18 ……are even number but number of digit in these number are 2. 2 is not odd number hence we gonna discard all these number
102 104 106 …. Are even number and number of digit in these number is 3 that is odd number hence we will count these number
1000 1002 1004….are even number and number of digit in these number is 4 that is even number hence we will not count these number…
Please let me know if you think differntly
Time O(n) Space(n). Finding a number which have Closest duplicate. Below method will return 5 as answer not 4 since 5 has closest duplicate then 4.
public static int FindClosestDuplicate(int[] arr)
{
if (arr == null) return -1;
Dictionary<int, int> elePos = new Dictionary<int, int>();
int minDiff = int.MaxValue;
int duplicate = -1;
for (int i = 0; i < arr.Length; i++)
{
if (elePos.ContainsKey(arr[i]))
{
int pos = elePos[arr[i]];
int diff = i - pos;
if (diff < minDiff)
{
minDiff = diff;
duplicate = arr[i];
}
}
else
elePos.Add(arr[i], i);
}
return duplicate;
}
}
One approach could be to store data in char matrix (char[][] ) and then start reading data from second column to n-1 column . Use Dictionary<int,char> to store result of column scan
Here are the rule of reading data in column
- Find max occurrence of character in selected column
- if you find single character having max occurrence then add that character to dictionary with column as key. For example while traverse first column you found A having max occurrence then you will add <1,A>
- In case all character have same occurrence add first character of selected column to dictionary. In case of Column 2 it will <2,C>
Now use this dictionary to get next character.
Space complexity will be O(n) and Time Complexity will be O(n) [as finding max occurrence require traversal of column].
Please let me know if I am missing any logic here...
// Build Binary Search tree by reading each element and add only unique element-
// now readback each element in inorder traversal to return back
// O(nlogn) Time and O(n + n) space complexity
// wrote on notedpad hence no compile error checking performed...
public int[] GetUniqeRecord(int[] arr)
{
if(arr == null) return null;
if(arr.Length == 1) return arr;
// Build Binary search tree
int count;
Node root = CreateBinaryTree(arr,out count);
return uniqueRecord(root);
// Readh binary search tree
}
public class Node
{
public int data{get;set;}
public Node left{get;set;}
public Node right{get;set;}
public Node(int data)
{
this.data = data;
}
}
publc int[] uniqueRecord(Node root,int count)
{
Stack s = new Stack();
int[] arr = new int[count];
Node n = root;
s.Push(n);
int i=0;
while(!s.IsEmpty() || n!= null)
{
if(n != null)
{
s.push(n);
arr[i++] = n.data;
n = n.left;
}
else
{
n= s.Pop();
n = n.right;
}
}
return arr;
}
public Node CreateBinaryTree(int[] arr,ref int cout)
{
Node root = null;
root = new Node(arr[0]);
Node temp = null;
node pre;
bool duplicate = false;
for(int i=1;i<arr.Legth-1;i++)
{
temp = root;
duplicate = false;
while(temp != null)
{
pre = temp;
if(arr[i] > temp.data)
{
temp = temp.right;
}
else if(arr[i] < temp.data)
{
temp = temp.left;
}
else
{
duplicate = true;
break;
}
}
if(!duplicatae)
{
if(arr[i] > pre.data)
pre.right = new Node(arr[i]);
else
pre.left = new Node(arr[i]);
count++;
}
}
}
// input ABCD
// output AABBCCCCBBAA
1) start reading from start to (lenght-1) and from Lenngth-1 to Start
public string GetNewString(string str)
{
if(str == null) return str;
if(str == "") return str;
StringBuilder sb1= new StringBuilder();
StringBuilder sb2= new StringBuilder();
for(int i=0,j=str.length-1;i<str.Lenght-1,j>=0;j--,i++)
{
sb1.Append(str[i]);
sb2.Append(str[j]);
}
return sb1.ToString() + sb2.ToString();
}
- James November 05, 2013//Get each word from string and then call another method to know if it is palindrom or not. if it is then increase the count
//Space complexity is O(1) & Processing will be O(M+K) where m is the number of word and k will be number of character.
public int FindNumberOfPalindrom(string s)
{
int _palindromCount = 0;
string[] words = s.Split(' ');
foreach (string word in words)
{
if (IsPalindrom(word))
_palindromCount++;
}
return _palindromCount;
}
public bool IsPalindrom(string word)
{
bool isPalindrom = true;
for (int i = 0, j = word.Length - 1; i <= word.Length/2; i++, j--)
{
if (word[i] != word[j])
isPalindrom = false;
}
return isPalindrom;
}
Please let me know what is the time complexity of this approach
public void SortArray(int[] a)
{
int temp;
int i = 0;
int j = 0;
// swap array element for 0
for (i = 0, j = a.Length - 1; i < j;)
{
if (a[i] == 0)
{
i++;
}
else if ((a[i] != 0 && a[j] == 0))
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
else if (a[i] != 0 && a[j] != 0)
{
j--;
}
}
// swap array element for 1
for (i = i + 1, j = a.Length - 1; i < j; )
{
if (a[i] == 1)
{
i++;
}
else if ((a[i] != 1 && a[j] == 1))
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
else if (a[i] != 1 && a[j] != 1)
{
j--;
}
}
}
public int GetStartPosOfLargestRepChar(string str)
{
Dictionary<char, int> dic = new Dictionary<char, int>();
int max = 0;
char maxChar = ' ';
int pos = -1;
for (int i = 0; i < str.Length; i++)
{
if (dic.ContainsKey(str[i]))
{
dic[str[i]]++;
if (dic[str[i]] > max)
{
max = dic[str[i]];
maxChar = str[i];
pos = i;
}
}
else
dic.Add(str[i], 1);
}
for (int k = 0; k < str.Length; k++)
if (str[k] == maxChar)
{
pos = k;
break;
}
return pos;
}
In C# string is immutable and you cannot modify existing string. So you have to use StringBuilder to do that. I am not sure if below answer is acceptable or not. Please provide your feedback.
public void ReplaceString()
{
string[] replaceList = new String[] { "UVW", "U", "UV" };
string str = "ABCDBCCDABCD";
int i = 0;
StringBuilder strBld = new StringBuilder();
foreach (string r in replaceList)
{
strBld.Clear();
i = 0;
for (i = 0; i < str.Length - 1; i++)
{
if (str[i] == 'B' && str[i + 1] == 'C')
{
strBld.Append(r);
i++;
}
else
{
strBld.Append(str[i]);
}
}
Console.WriteLine(" Replace with {0} and new string {1}", r, strBld);
}
}
Thanks for you reply CasaPanacea. I understand the question only after understanding your code :)
- James July 12, 2015