• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Find Pythagorean Triplets in an array in O(N)

March 27, 2014 by Dhaval Dave

Find Pythagorean Triplets in an array

We have an array in which random integers are there. we need to find Pythagorean triplets.
which solves equation a^2 + b^2 = c^2.
Method 1 : Brute Force Method
Loop the array for three times and find a, b, and c which are solving equation.
Time complexity : O(N^3)

Method 2 : Using Hash Map to search.

  1) Create two loops and find all pairs.
  2) Find +C, -C = SquareRoot ( A^2 + B^2)
  3) Using Hash find whether C is present in Array or not.
  4) If C is present print Triplet A, B, C 
  5) Else continue till both loop completes.

Method 3 : Using Maths 

We know that
a = m^2 – n^2, b = 2mn, c = m^2 + n^2
From here you can get clue..
If not .. read further.

1)Sort the array in O(N log N) time.
2)For each element B, find the prime factorization. such that  
b = 2mn , m > n. m and n are prime
3)Calculate C = m^2 + n^2 , A= m^2 - n^2
4)With Hashmap find If C and A are in Array. Then Print Triplet C,A,B
5)Else Continue.

Explanation :

Consider Array : {3,6,8,5,10,4,12,14}

Step 1) 
Finding prime factorization such that b=2mn.
3 - not possible.
6 - 2*1*3 so m=3, n=1
8 - 2*2*2 so m=2,n=2 (not allowed , as they need to be co-prime)
5 - not possible
10 - 2*1*5 so m=5, n=1
4 - 2*1*2 so m=2, n=1 ...

Step 2) 

6 - 2*1*3 so m=3, n=1 m^2 + n^2 = 10 , m^2 - n^2 = 8 , 
both numbers are present in array can be found in O(1) 
with Hash.
    C = 10, A =8 and B = 6

=> similarly for 3,4,5 we can find 
m=2,n=1, B=4, C=5, A=3.

You can write and code for this
Best luck

Similar Articles

Filed Under: Amazon Interview Question, Flipkart Interview Questions, Interview Questions, problem Tagged With: Mathematical

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

How strtok() Works

Print all nodes that are at distance k from a leaf node

Leetcode: Edit Distance

Get Minimum element in O(1) from input numbers or Stack

Rectangular chocolate bar Create at least one piece which consists of exactly nTiles tiles

Given array of 0’s and 1’s. All 0’s are coming first followed by 1’s. find the position of first 1

Knight Tour Problem (Graph – Breadth First Search)

Handle duplicates in Binary Search Tree

Possible sizes of bus to carry n groups of friends

Level order traversal in Spiral form

Adobe Interview Questions 8 month Exp

Singly linked list

Stock Buy Sell to Maximize Profit

flattens 2 D linked list to a single sorted link list

Doubly linked list

Subset Sum Problem Dynamic programming

Number of Islands BFS/DFS

write a c program that given a set a of n numbers and another number x determines whether or not there exist two elements in s whose sum is exactly x

Facebook Interview Question : Interleave List

Linked List V/S Binary Search Tree

Find Nearest Minimum number in left side in O(n)

Maximum size of square sub matrix with all 1’s in a binary matrix

Interfaces in C++ (Abstract Classes in C++)

Reliance Jio Software Developer Interview Experience

Daughter’s Age VeryGood Puzzle

‘N’ Story Building, with 1,2,3 steps how many ways can a person reach top of building.

Add Sub Multiply very large number stored as string

Given Set of words or A String find whether chain is possible from these words or not

Word Break Problem

CodeChef Code SGARDEN

Copyright © 2023 · Genesis Framework · WordPress · Log in