DIFFERENCE TRICK

In Manish's restaurant, a waiter is training. Since the waiter isn't good at arithmetic, sometimes he gives guests wrong change. Manish gives him a simple problem. What is A-B (A minus B) ?
Surprisingly, his answer is wrong. To be more precise, his answer has exactly one wrong digit. Can you imagine this? Can you make the same mistake in this problem?
INPUT
An input contains 2 integers A and B.
OUTPUT
Print a wrong answer of A-B. Your answer must be a positive integer containing the same number of digits as the correct answer, and exactly one digit must differ from the correct answer. Leading zeros are not allowed. If there are multiple answers satisfying the above conditions, anyone will do.
CONSTRAINTS
1 ≤ B < A ≤ 10000

---

Sample Input

(Plaintext Link)

5858 1234

Sample Output

(Plaintext Link)

1624

SOLUTION:

#include<stdio.h>
int main()
{
    int a,b,diff;
    scanf("%d%d",&a,&b);
    diff=a-b;
    int i=diff%10;
    if(i<9)
     diff++;
    else
     diff--;
   
    printf("%d",diff);
    return 0;
} 

Monk and his Friend

Monk has a very good friend, Puchi. As weird as his name, are the games he plays.
One fine day, they decided to play a game to test how diverse their choices are. Both of them choose exactly one integer each. Monk chooses an integer M and Puchi chooses an integer P.
The diversity of their choices is defined as the number of bits whose status is different in the binary representation of Mand P , i.e. , count of bits that are ,either set in M and unset in P or set in P and unset in M.
Find the answer to their game.

Input:
First line contains T. T test cases follow.
Each test case consists of 2 space-separated integers P and M.

Output:
Print the answer to each test case in a new line.

Constraints:
1 ≤ T ≤ 10⁴
0 ≤ M, P ≤ 10¹⁶

---

Sample Input

(Plaintext Link)

4
1 4
3 3
5 1
8 7

Sample Output

(Plaintext Link)

2
0
1
4

Explanation

1 (0001) and 4 (0100) differ in 2 bits.
The two numbers are identical.
5 (0101) and 1(0001) differ in 1 bit.
8 (1000) and 7(0111) differ in 4 bits.

#include <stdio.h>

int main()
{
   int t,count;
   scanf("%d",&t);
   while(t--)
   {
   long long int a,b,k;
    scanf("%lld %lld",&a,&b);
    if(a==b)
     printf("0\n");
    else
    {
    k=a^b;count=0;
    while( k )
        {
        k = k&(k-1);
           count++;
        }
    printf("%d\n",count);
    }
   }
    return 0;
}

REFER LINK:https://www.hackerearth.com/code-monk-bit-manipulation/algorithm/monk-and-his-friend/

Sherlock and Squares

Problem Statement

Watson gives two integers (A and B) to Sherlock and asks if he can count the number of square integersbetween A and B (both inclusive).
Note: A square integer is an integer which is the square of any integer. For example, 1, 4, 9, and 16 are some of the square integers as they are squares of 1, 2, 3, and 4, respectively.
Input Format
The first line contains T, the number of test cases. T test cases follow, each in a new line.
Each test case contains two space-separated integers denoting A and B.
Output Format
For each test case, print the required answer in a new line.
Constraints
1≤T≤100
1≤A≤B≤109
Sample Input

2
3 9
17 24

Sample output

2
0

Explanation
Test Case #00: In range [3,9], 4 and 9 are the two square numbers.
Test Case #01: In range [17,24], there are no square numbers.
CODE:
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {
    int a,b,t,i,j,count=0;
 scanf("%d",&t);
    while(t!=0)
        {
       
        scanf("%d%d",&a,&b);
            for(j=0;j<=sqrt(b);j++)
                {
                if(j*j>=a&&j*j<=b)
                    {
                    count++;
                }
            }
        printf("%d\n",count);
        count=0;
       t--;
        }
  

      return 0;
}
REFER LINK:https://www.hackerrank.com/challenges/sherlock-and-squares/

Check if a given number is sparse or not

A number is said to be a sparse number if in binary representation of the number no two or more consecutive bits are set. Write a function to check if a given number is Sparse or not.
consider x=3
binary form of 3 is 0011
step 1:right shift 'x'  then 0001 
step 2:do AND product
             0011
             0001
            ----------
             0001
           ----------
step3:
          if     
              the answer is 0 then it is sparse number
         else
              it is not a sparse number 
CODE:

#include <stdio.h>

int main()

{

   int x;

   scanf("%d",&x);

   if(x & (x >> 1))

       printf("not sparse");

   else

       printf("sparse");

    return 0;

}

Find XOR of two number without using XOR operator

A Simple Solution is to traverse all bits one by one. For every pair of bits, check if both are same, set the corresponding bit as 0 in output, otherwise set as 1.

SOLUTION IN C++

#include <iostream>

using namespace std;

int main()

{

   int x,y,b1,b2,i;

   int res=0,ans=0;

   cin>>x>>y;

   for(i=31;i>=0;i--)

   {

       bool b1=x & (1 << i);

       bool b2=y & (1 << i);

       bool x_y = (b1 & b2) ? 0 : (b1 | b2);  

        res <<= 1;

        res |= x_y;

    

   }

  cout<<"xor is "<<res;

    return 0;

}

OUTPUT:

IS FIBO........

Problem Statement

You are given an integer, N. Write a program to determine if N is an element of the Fibonacci sequence.

The first few elements of the Fibonacci sequence are 0,1,1,2,3,5,8,13,⋯. A Fibonacci sequence is one where every element is a sum of the previous two elements in the sequence. The first two elements are 0 and 1.

Formally: 

fib0fib1⋮fibn=0=1=fibn−1+fibn−2∀n>1

Input Format 
The first line contains T, number of test cases. 
T lines follow. Each line contains an integer N.

Output Format 
Display IsFibo if N is a Fibonacci number and IsNotFibo if it is not. The output for each test case should be displayed in a new line.

Constraints 
1≤T≤105 
1≤N≤1010

Sample Input

3
5
7
8

Sample Output

IsFibo
IsNotFibo
IsFibo

Explanation 
5 is a Fibonacci number given by fib5=3+2 
7 is not a Fibonacci number 
8 is a Fibonacci number given by fib6=5+3

SOLUTION:

import java.math.BigDecimal;

import java.math.RoundingMode;

import java.util.*;

public class FibonacciTester {

    private static BigDecimal zero = BigDecimal.valueOf(0);

    private static BigDecimal one = BigDecimal.valueOf(1);

    private static BigDecimal two = BigDecimal.valueOf(2);

    private static BigDecimal four = BigDecimal.valueOf(4);

    private static BigDecimal five = BigDecimal.valueOf(5);

    public static void main(String[] args) {

       

       Scanner sc=new Scanner(System.in);

       int t=sc.nextInt(); 

       while(t!=0){

        BigDecimal num =sc.nextBigDecimal();

        if (isFibonacci(num)) {

            System.out.println("IsFibo");

        } else {

            System.out.println("IsNotFibo");

        }

       t=t-1;

       }

    }   

        

    public static boolean isFibonacci(BigDecimal num) {

        if (num.compareTo(zero) <= 0) {

            return false;

        }

        BigDecimal base = num.multiply(num).multiply(five);

        BigDecimal possibility1 = base.add(four);

        BigDecimal possibility2 = base.subtract(four);

        return (isPerfectSquare(possibility1) || isPerfectSquare(possibility2));

    }

    public static boolean isPerfectSquare(BigDecimal num) {

        BigDecimal low = zero;

        BigDecimal high = num;

        while (low.compareTo(high) <= 0) {

            BigDecimal mid = low.add(high).divide(two).setScale(0, RoundingMode.DOWN);

            BigDecimal square = mid.multiply(mid);

            int comparison = square.compareTo(num);

            if (comparison == 0) {

                return true;

            } else if (comparison > 0) {

                high = mid.subtract(one);

            } else {

                low = mid.add(one);

            }

        }

        return false;

    }

}