Unlucky Numbers

There are few numbers considered to be unlucky(It contains only 4 and 7. ). Our goal is to find count of such numbers in the range of positive integers a and b.
For Example:
Input:: a = 10 b = 20
Output:: 0

Input:: a = 30 b = 50
Output:: 2 (44, 47)

Source: Topcoder

Solution:
Idea is to find the number of digits in a, let that be n. now
1. Start with a number which has n 4s, so if n is 2 start with 44, if n i 5 start with 44444.
2. increment the count.
3. If the curr number greater than b break and print the count.
4. Now start with the curr digit(last digit) of curr number, if the curr is 4 change it to 7 and
go to step2. if it is 7 set the curr digit to 4 and go to next digit to the left. do this step 4 again
until u reach a number greater than b, or reach a place where all digits are 7s and then u add 4
to it and go to step2.


Example:
a = 10 b = 500
actual numbers are 44, 47, 74, 77, 444, 447, 474, 477

Ideal string

An ideal string is a string where the 1-based index of the first occurrence of each letter is equal to the number of occurrences of that letter in the string. For example, the "BAOOOA" is an ideal string (quotes for clarity only). The letter 'B' appears 1 time, and its index is 1. The letter 'A' occurs 2 times and its first index is 2. The letter 'O' occurs 3 times and its first index is 3.

Given an int length, return the lexicographically smallest ideal string of that length containing only uppercase letters ('A'-'Z'). If there are no such ideal strings of that length, return an empty String instead.

Source: TopCoder

Solution:
To solve this problem we need to come up with a formula which tells us whether it is possible to have such a string at all or not. As we can see that element at index 1 must appear once, index 2 must appear twice and index n must appear n times.

So total length of string = length = 1 + 2 + .... n
hence n*(n+1)/2 = length
We should be able to represent the length as above, if we cannot then empty string can be returned.
If we can represent we should do the following:
1. Find n from the above equation.
2. Fill "A" in the 1st index and fill the remainder(0) of "A" in the n+1 th index.
3. Fill "B" in the 2nd index and fill the remainder(1) of "B" in the index after the previous fill.
3. Fill "C" in the 3rd index and fill the remainder(2) of "C" in the index after the previous fill.
........
n. Fill "n" in the nth index and fill the remainder (n-1) of "n" in the index after previous fill

After the above operation is done, print the array.

Next Palindrome Problem

Find the next palindrome. Input is an integer and output should be the palindrome integer which is higher than the input.

Example:
Input: 12345
Output:12421
Input:111
Output: 121

Solution:
Let the Input be "ABCDEFGH". Now divide it into two equal parts "ABCD" and "EFGH". let us call the higher part as "ABCD" and lower part as "EFGH". Now reverse the higher part to get "DCBA". Check if "DCBA" greater than "EFGH" or not.
Case 1: DCBA is greater than EFGH
return "ABCDDCBA" as the output.
Case 2: DCBA is lower than or equal to EFGH
Add 10000 to "ABCDEFGH" to "HIJKEFGH" and apply the above logic to return "HIJKKJIH"
10000 is added to ensure that the middle digit is changed. Added index is generally 10^(numOfDigits/2).

Example 1:
112100
higher = 112
lower = 110
reverse higher = 211
So output 112211

Example 2:
1121
higher = 11
lower = 21
reverse higher = 11
So add 100 to change the lowest of the higher part. to get 1221. So output 1221 as the next palindrome.

Example 3:
45621
higher = 45
lower = 21
reverse higher = 54
so return 45654


Example 4:
45678
higher = 45
lower = 78
reverse higher = 54
so add 100 to get 45778 . so return 45754.